X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStackSlotColoring.cpp;h=51f4d0e6817216f487130a2214054e60e7bf7286;hb=0d0bb8e27bde93487a50f04b0d2483228bf9f92e;hp=39b0c59a1bf9a91ac14ac4b9afbbd2e8d2c9f111;hpb=3b2c01723c2f7270e357f3b8502bb80572b3e644;p=oota-llvm.git diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index 39b0c59a1bf..51f4d0e6817 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -11,45 +11,55 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "stackcoloring" #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/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "stackslotcoloring" + 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 -EnableDCE("enable-ssc-dce", - cl::init(false), cl::Hidden, - cl::desc("Enable slot coloring DCE")); +static cl::opt DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); -STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); -STATISTIC(NumDeadAccesses, - "Number of trivially dead stack accesses eliminated"); +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; @@ -69,42 +79,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) {} - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + StackSlotColoring() : + MachineFunctionPass(ID), NextColor(-1) { + initializeStackSlotColoringPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); - - AU.addPreservedID(MachineLoopInfoID); + AU.addRequired(); + AU.addPreserved(); AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } - virtual bool runOnMachineFunction(MachineFunction &MF); - virtual const char* getPassName() const { - return "Stack Slot Coloring"; - } + bool runOnMachineFunction(MachineFunction &MF) override; private: - bool InitializeSlots(); + void InitializeSlots(); + void ScanForSpillSlotRefs(MachineFunction &MF); bool OverlapWithAssignments(LiveInterval *li, int Color) const; int ColorSlot(LiveInterval *li); bool ColorSlots(MachineFunction &MF); - bool removeDeadStores(MachineBasicBlock* MBB); + 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 @@ -116,12 +134,49 @@ 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 FixedStackPseudoSourceValue *FSV = + dyn_cast_or_null( + MMO->getPseudoValue())) { + 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); @@ -129,10 +184,20 @@ bool StackSlotColoring::InitializeSlots() { UsedColors.resize(LastFI); Assignments.resize(LastFI); + typedef std::iterator_traits::value_type Pair; + SmallVector Intervals; + Intervals.reserve(LS->getNumIntervals()); + for (auto &I : *LS) + Intervals.push_back(&I); + std::sort(Intervals.begin(), Intervals.end(), + [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; }); + // Gather all spill slots into a list. - for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { - LiveInterval &li = i->second; - int FI = li.getStackSlotIndex(); + DEBUG(dbgs() << "Spill slot intervals:\n"); + for (auto *I : Intervals) { + LiveInterval &li = I->second; + DEBUG(li.dump()); + int FI = TargetRegisterInfo::stackSlot2Index(li.reg); if (MFI->isDeadObjectIndex(FI)) continue; SSIntervals.push_back(&li); @@ -140,20 +205,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)) @@ -191,8 +256,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 @@ -210,61 +275,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 PseudoSourceValue *NewSV = MF.getPSVManager().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.isFI()) - continue; - int FI = MO.getIndex(); - if (FI < 0) - continue; - int NewFI = SlotMapping[FI]; - if (NewFI == -1) - continue; - MO.setIndex(NewFI); - - // Update the MachineMemOperand for the new memory location. - // FIXME: We need a better method of managing these too. - SmallVector MMOs(MI.memoperands_begin(), - MI.memoperands_end()); - MI.clearMemOperands(MF); - const Value *OldSV = PseudoSourceValue::getFixedStack(FI); - for (unsigned i = 0, e = MMOs.size(); i != e; ++i) { - if (MMOs[i].getValue() == OldSV) { - MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), - MMOs[i].getFlags(), MMOs[i].getOffset(), - MMOs[i].getSize(), MMOs[i].getAlignment()); - MI.addMemOperand(MF, MMO); - } else - MI.addMemOperand(MF, MMOs[i]); - } - } - } + 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); } @@ -272,12 +344,35 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { return true; } -/// removeDeadStores - Scan through a basic block and look for loads followed +/// 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) { +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; @@ -286,49 +381,83 @@ bool StackSlotColoring::removeDeadStores(MachineBasicBlock* MBB) { for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { - MachineBasicBlock::iterator NextMI = next(I); - if (NextMI == MBB->end()) continue; - + 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 = std::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; - - ++NumDeadAccesses; + + ++NumDead; changed = true; - - if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { - ++NumDeadAccesses; + + if (NextMI->findRegisterUseOperandIdx(LoadReg, true, nullptr) != -1) { + ++NumDead; toErase.push_back(I); } - + toErase.push_back(NextMI); ++I; } - - for (SmallVector::iterator I = toErase.begin(), + + 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(); + TII = MF.getSubtarget().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(); @@ -337,10 +466,5 @@ bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { Assignments[i].clear(); Assignments.clear(); - if (EnableDCE) { - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) - Changed |= removeDeadStores(I); - } - return Changed; }