X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStackSlotColoring.cpp;h=77c7047cde5502e77b22e59fab363205dae4a9b2;hb=5be77762a3aa434ee877b0a03b98b5c3a7571918;hp=1b5d41795cc2bed45148b54f1b142ab8f6824657;hpb=bbeeb2a61ea19fbb5449260165b56c40fdc4860b;p=oota-llvm.git diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index 1b5d41795cc..77c7047cde5 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -11,34 +11,54 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "stackcoloring" +#define DEBUG_TYPE "stackslotcoloring" #include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineMemOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/PseudoSourceValue.h" +#include "llvm/IR/Module.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" #include using namespace llvm; static cl::opt DisableSharing("no-stack-slot-sharing", cl::init(false), cl::Hidden, - cl::desc("Surpress slot sharing during stack coloring")); + cl::desc("Suppress slot sharing during stack coloring")); + +static cl::opt DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); -STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); +STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); +STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); namespace { - class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { + class StackSlotColoring : public MachineFunctionPass { LiveStacks* LS; MachineFrameInfo *MFI; + const TargetInstrInfo *TII; + const MachineBlockFrequencyInfo *MBFI; // SSIntervals - Spill slot intervals. std::vector SSIntervals; + // SSRefs - Keep a list of MachineMemOperands for each spill slot. + // MachineMemOperands can be shared between instructions, so we need + // to be careful that renames like [FI0, FI1] -> [FI1, FI2] do not + // become FI0 -> FI1 -> FI2. + SmallVector, 16> SSRefs; + // OrigAlignments - Alignments of stack objects before coloring. SmallVector OrigAlignments; @@ -58,39 +78,50 @@ namespace { BitVector UsedColors; // Assignments - Color to intervals mapping. - SmallVector,16> Assignments; + SmallVector, 16> Assignments; public: static char ID; // Pass identification - StackSlotColoring() : MachineFunctionPass(&ID), NextColor(-1) {} - + StackSlotColoring() : + MachineFunctionPass(ID), NextColor(-1) { + initializeStackSlotColoringPass(*PassRegistry::getPassRegistry()); + } + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); - AU.setPreservesAll(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } virtual bool runOnMachineFunction(MachineFunction &MF); - virtual const char* getPassName() const { - return "Stack Slot Coloring"; - } private: - bool InitializeSlots(); + void InitializeSlots(); + void ScanForSpillSlotRefs(MachineFunction &MF); bool OverlapWithAssignments(LiveInterval *li, int Color) const; int ColorSlot(LiveInterval *li); bool ColorSlots(MachineFunction &MF); + void RewriteInstruction(MachineInstr *MI, SmallVectorImpl &SlotMapping, + MachineFunction &MF); + bool RemoveDeadStores(MachineBasicBlock* MBB); }; } // end anonymous namespace char StackSlotColoring::ID = 0; +char &llvm::StackSlotColoringID = StackSlotColoring::ID; -static RegisterPass -X("stack-slot-coloring", "Stack Slot Coloring"); - -FunctionPass *llvm::createStackSlotColoringPass() { - return new StackSlotColoring(); -} +INITIALIZE_PASS_BEGIN(StackSlotColoring, "stack-slot-coloring", + "Stack Slot Coloring", false, false) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_PASS_DEPENDENCY(LiveStacks) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_END(StackSlotColoring, "stack-slot-coloring", + "Stack Slot Coloring", false, false) namespace { // IntervalSorter - Comparison predicate that sort live intervals by @@ -102,12 +133,50 @@ namespace { }; } +/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot +/// references and update spill slot weights. +void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { + SSRefs.resize(MFI->getObjectIndexEnd()); + + // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. + for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); + MBBI != E; ++MBBI) { + MachineBasicBlock *MBB = &*MBBI; + for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); + MII != EE; ++MII) { + MachineInstr *MI = &*MII; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isFI()) + continue; + int FI = MO.getIndex(); + if (FI < 0) + continue; + if (!LS->hasInterval(FI)) + continue; + LiveInterval &li = LS->getInterval(FI); + if (!MI->isDebugValue()) + li.weight += LiveIntervals::getSpillWeight(false, true, MBFI, MI); + } + for (MachineInstr::mmo_iterator MMOI = MI->memoperands_begin(), + EE = MI->memoperands_end(); MMOI != EE; ++MMOI) { + MachineMemOperand *MMO = *MMOI; + if (const Value *V = MMO->getValue()) { + if (const FixedStackPseudoSourceValue *FSV = + dyn_cast(V)) { + int FI = FSV->getFrameIndex(); + if (FI >= 0) + SSRefs[FI].push_back(MMO); + } + } + } + } + } +} + /// InitializeSlots - Process all spill stack slot liveintervals and add them /// to a sorted (by weight) list. -bool StackSlotColoring::InitializeSlots() { - if (LS->getNumIntervals() < 2) - return false; - +void StackSlotColoring::InitializeSlots() { int LastFI = MFI->getObjectIndexEnd(); OrigAlignments.resize(LastFI); OrigSizes.resize(LastFI); @@ -116,9 +185,11 @@ bool StackSlotColoring::InitializeSlots() { Assignments.resize(LastFI); // Gather all spill slots into a list. + DEBUG(dbgs() << "Spill slot intervals:\n"); for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { LiveInterval &li = i->second; - int FI = li.getStackSlotIndex(); + DEBUG(li.dump()); + int FI = TargetRegisterInfo::stackSlot2Index(li.reg); if (MFI->isDeadObjectIndex(FI)) continue; SSIntervals.push_back(&li); @@ -126,20 +197,20 @@ bool StackSlotColoring::InitializeSlots() { OrigSizes[FI] = MFI->getObjectSize(FI); AllColors.set(FI); } + DEBUG(dbgs() << '\n'); // Sort them by weight. std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); // Get first "color". NextColor = AllColors.find_first(); - return true; } /// OverlapWithAssignments - Return true if LiveInterval overlaps with any /// LiveIntervals that have already been assigned to the specified color. bool StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { - const SmallVector &OtherLIs = Assignments[Color]; + const SmallVectorImpl &OtherLIs = Assignments[Color]; for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { LiveInterval *OtherLI = OtherLIs[i]; if (OtherLI->overlaps(*li)) @@ -177,8 +248,8 @@ int StackSlotColoring::ColorSlot(LiveInterval *li) { // Record the assignment. Assignments[Color].push_back(li); - int FI = li->getStackSlotIndex(); - DOUT << "Assigning fi #" << FI << " to fi #" << Color << "\n"; + int FI = TargetRegisterInfo::stackSlot2Index(li->reg); + DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n"); // Change size and alignment of the allocated slot. If there are multiple // objects sharing the same slot, then make sure the size and alignment @@ -196,45 +267,68 @@ int StackSlotColoring::ColorSlot(LiveInterval *li) { /// operands in the function. bool StackSlotColoring::ColorSlots(MachineFunction &MF) { unsigned NumObjs = MFI->getObjectIndexEnd(); - std::vector SlotMapping(NumObjs, -1); + SmallVector SlotMapping(NumObjs, -1); + SmallVector SlotWeights(NumObjs, 0.0); + SmallVector, 16> RevMap(NumObjs); + BitVector UsedColors(NumObjs); + DEBUG(dbgs() << "Color spill slot intervals:\n"); bool Changed = false; for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { LiveInterval *li = SSIntervals[i]; - int SS = li->getStackSlotIndex(); + int SS = TargetRegisterInfo::stackSlot2Index(li->reg); int NewSS = ColorSlot(li); + assert(NewSS >= 0 && "Stack coloring failed?"); SlotMapping[SS] = NewSS; + RevMap[NewSS].push_back(SS); + SlotWeights[NewSS] += li->weight; + UsedColors.set(NewSS); Changed |= (SS != NewSS); } + DEBUG(dbgs() << "\nSpill slots after coloring:\n"); + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { + LiveInterval *li = SSIntervals[i]; + int SS = TargetRegisterInfo::stackSlot2Index(li->reg); + li->weight = SlotWeights[SS]; + } + // Sort them by new weight. + std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); + +#ifndef NDEBUG + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) + DEBUG(SSIntervals[i]->dump()); + DEBUG(dbgs() << '\n'); +#endif + if (!Changed) return false; - // Rewrite all MO_FrameIndex operands. - // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. - for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); - MBB != E; ++MBB) { + // Rewrite all MachineMemOperands. + for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { + int NewFI = SlotMapping[SS]; + if (NewFI == -1 || (NewFI == (int)SS)) + continue; + + const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI); + SmallVectorImpl &RefMMOs = SSRefs[SS]; + for (unsigned i = 0, e = RefMMOs.size(); i != e; ++i) + RefMMOs[i]->setValue(NewSV); + } + + // Rewrite all MO_FrameIndex operands. Look for dead stores. + for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); + MBBI != E; ++MBBI) { + MachineBasicBlock *MBB = &*MBBI; for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); - MII != EE; ++MII) { - MachineInstr &MI = *MII; - for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI.getOperand(i); - if (!MO.isFrameIndex()) - continue; - int FI = MO.getIndex(); - if (FI < 0) - continue; - FI = SlotMapping[FI]; - if (FI == -1) - continue; - MO.setIndex(FI); - } - } + MII != EE; ++MII) + RewriteInstruction(MII, SlotMapping, MF); + RemoveDeadStores(MBB); } // Delete unused stack slots. while (NextColor != -1) { - DOUT << "Removing unused stack object fi #" << NextColor << "\n"; + DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n"); MFI->RemoveStackObject(NextColor); NextColor = AllColors.find_next(NextColor); } @@ -242,18 +336,120 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { return true; } +/// RewriteInstruction - Rewrite specified instruction by replacing references +/// to old frame index with new one. +void StackSlotColoring::RewriteInstruction(MachineInstr *MI, + SmallVectorImpl &SlotMapping, + MachineFunction &MF) { + // Update the operands. + for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isFI()) + continue; + int OldFI = MO.getIndex(); + if (OldFI < 0) + continue; + int NewFI = SlotMapping[OldFI]; + if (NewFI == -1 || NewFI == OldFI) + continue; + MO.setIndex(NewFI); + } + + // The MachineMemOperands have already been updated. +} + + +/// RemoveDeadStores - Scan through a basic block and look for loads followed +/// by stores. If they're both using the same stack slot, then the store is +/// definitely dead. This could obviously be much more aggressive (consider +/// pairs with instructions between them), but such extensions might have a +/// considerable compile time impact. +bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { + // FIXME: This could be much more aggressive, but we need to investigate + // the compile time impact of doing so. + bool changed = false; + + SmallVector toErase; + + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); + I != E; ++I) { + if (DCELimit != -1 && (int)NumDead >= DCELimit) + break; + + int FirstSS, SecondSS; + if (TII->isStackSlotCopy(I, FirstSS, SecondSS) && + FirstSS == SecondSS && + FirstSS != -1) { + ++NumDead; + changed = true; + toErase.push_back(I); + continue; + } + + MachineBasicBlock::iterator NextMI = llvm::next(I); + if (NextMI == MBB->end()) continue; + + unsigned LoadReg = 0; + unsigned StoreReg = 0; + if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; + if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; + if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; + + ++NumDead; + changed = true; + + if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { + ++NumDead; + toErase.push_back(I); + } + + toErase.push_back(NextMI); + ++I; + } + + for (SmallVectorImpl::iterator I = toErase.begin(), + E = toErase.end(); I != E; ++I) + (*I)->eraseFromParent(); + + return changed; +} + + bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { - DOUT << "********** Stack Slot Coloring **********\n"; + DEBUG({ + dbgs() << "********** Stack Slot Coloring **********\n" + << "********** Function: " << MF.getName() << '\n'; + }); MFI = MF.getFrameInfo(); + TII = MF.getTarget().getInstrInfo(); LS = &getAnalysis(); + MBFI = &getAnalysis(); bool Changed = false; - if (InitializeSlots()) - Changed = ColorSlots(MF); + + unsigned NumSlots = LS->getNumIntervals(); + if (NumSlots == 0) + // Nothing to do! + return false; + + // If there are calls to setjmp or sigsetjmp, don't perform stack slot + // coloring. The stack could be modified before the longjmp is executed, + // resulting in the wrong value being used afterwards. (See + // .) + if (MF.exposesReturnsTwice()) + return false; + + // Gather spill slot references + ScanForSpillSlotRefs(MF); + InitializeSlots(); + Changed = ColorSlots(MF); NextColor = -1; SSIntervals.clear(); + for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) + SSRefs[i].clear(); + SSRefs.clear(); OrigAlignments.clear(); OrigSizes.clear(); AllColors.clear();