X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=lib%2FCodeGen%2FStackSlotColoring.cpp;h=8043556349808b18b78c801d88d1488b6548f3db;hb=174e597d466547d34cf8fcd2a95976e0cf5ebbac;hp=24bd028afda59176be060718870afe00fa32c6dd;hpb=3f32d65912b4da23793dab618d981be2ce11c331;p=oota-llvm.git diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index 24bd028afda..80435563498 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -1,4 +1,4 @@ -//===-- StackSlotColoring.cpp - Sinking for machine instructions ----------===// +//===-- StackSlotColoring.cpp - Stack slot coloring pass. -----------------===// // // The LLVM Compiler Infrastructure // @@ -12,13 +12,23 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "stackcoloring" +#include "VirtRegMap.h" +#include "llvm/Function.h" +#include "llvm/Module.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" -#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineMemOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include @@ -27,22 +37,39 @@ 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 +ColorWithRegsOpt("color-ss-with-regs", + cl::init(false), cl::Hidden, + cl::desc("Color stack slots with free registers")); + -static cl::opt -DeleteLimit("slot-delete-limit", cl::init(-1), cl::Hidden, - cl::desc("Stack coloring slot deletion limit")); +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(NumRegRepl, "Number of stack slot refs replaced with reg refs"); +STATISTIC(NumLoadElim, "Number of loads eliminated"); +STATISTIC(NumStoreElim, "Number of stores eliminated"); +STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); namespace { - class VISIBILITY_HIDDEN StackSlotColoring : public MachineFunctionPass { + class StackSlotColoring : public MachineFunctionPass { + bool ColorWithRegs; LiveStacks* LS; + VirtRegMap* VRM; MachineFrameInfo *MFI; + MachineRegisterInfo *MRI; + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + const MachineLoopInfo *loopInfo; // SSIntervals - Spill slot intervals. std::vector SSIntervals; + // SSRefs - Keep a list of frame index references for each spill slot. + SmallVector, 16> SSRefs; + // OrigAlignments - Alignments of stack objects before coloring. SmallVector OrigAlignments; @@ -62,14 +89,25 @@ namespace { BitVector UsedColors; // Assignments - Color to intervals mapping. - SmallVector,16> Assignments; + SmallVector, 16> Assignments; public: static char ID; // Pass identification - StackSlotColoring() : MachineFunctionPass((intptr_t)&ID), NextColor(-1) {} + StackSlotColoring() : + MachineFunctionPass(&ID), ColorWithRegs(false), NextColor(-1) {} + StackSlotColoring(bool RegColor) : + MachineFunctionPass(&ID), ColorWithRegs(RegColor), NextColor(-1) {} virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -79,10 +117,29 @@ namespace { } private: - bool InitializeSlots(); + void InitializeSlots(); + bool CheckForSetJmpCall(const MachineFunction &MF) const; + void ScanForSpillSlotRefs(MachineFunction &MF); bool OverlapWithAssignments(LiveInterval *li, int Color) const; int ColorSlot(LiveInterval *li); bool ColorSlots(MachineFunction &MF); + bool ColorSlotsWithFreeRegs(SmallVector &SlotMapping, + SmallVector, 16> &RevMap, + BitVector &SlotIsReg); + void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, + MachineFunction &MF); + bool PropagateBackward(MachineBasicBlock::iterator MII, + MachineBasicBlock *MBB, + unsigned OldReg, unsigned NewReg); + bool PropagateForward(MachineBasicBlock::iterator MII, + MachineBasicBlock *MBB, + unsigned OldReg, unsigned NewReg); + void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, + unsigned Reg, const TargetRegisterClass *RC, + SmallSet &Defs, + MachineFunction &MF); + bool AllMemRefsCanBeUnfolded(int SS); + bool RemoveDeadStores(MachineBasicBlock* MBB); }; } // end anonymous namespace @@ -91,8 +148,8 @@ char StackSlotColoring::ID = 0; static RegisterPass X("stack-slot-coloring", "Stack Slot Coloring"); -FunctionPass *llvm::createStackSlotColoringPass() { - return new StackSlotColoring(); +FunctionPass *llvm::createStackSlotColoringPass(bool RegColor) { + return new StackSlotColoring(RegColor); } namespace { @@ -105,12 +162,68 @@ namespace { }; } -/// InitializeSlots - Process all spill stack slot liveintervals and add them -/// to a sorted (by weight) list. -bool StackSlotColoring::InitializeSlots() { - if (LS->getNumIntervals() < 2) +/// CheckForSetJmpCall - Return true if there's a call to setjmp/sigsetjmp in +/// this function. +bool StackSlotColoring::CheckForSetJmpCall(const MachineFunction &MF) const { + const Function *F = MF.getFunction(); + const Module *M = F->getParent(); + const Function *SetJmp = M->getFunction("setjmp"); + const Function *SigSetJmp = M->getFunction("sigsetjmp"); + + if (!SetJmp && !SigSetJmp) return false; + if (SetJmp && !SetJmp->use_empty()) + for (Value::const_use_iterator + I = SetJmp->use_begin(), E = SetJmp->use_end(); I != E; ++I) + if (const CallInst *CI = dyn_cast(I)) + if (CI->getParent()->getParent() == F) + return true; + + if (SigSetJmp && !SigSetJmp->use_empty()) + for (Value::const_use_iterator + I = SigSetJmp->use_begin(), E = SigSetJmp->use_end(); I != E; ++I) + if (const CallInst *CI = dyn_cast(I)) + if (CI->getParent()->getParent() == F) + return true; + + return false; +} + +/// 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; + unsigned loopDepth = loopInfo->getLoopDepth(MBB); + 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, loopDepth); + SSRefs[FI].push_back(MI); + } + } + } +} + +/// InitializeSlots - Process all spill stack slot liveintervals and add them +/// to a sorted (by weight) list. +void StackSlotColoring::InitializeSlots() { int LastFI = MFI->getObjectIndexEnd(); OrigAlignments.resize(LastFI); OrigSizes.resize(LastFI); @@ -119,8 +232,10 @@ 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; + DEBUG(li.dump()); int FI = li.getStackSlotIndex(); if (MFI->isDeadObjectIndex(FI)) continue; @@ -129,13 +244,13 @@ 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 @@ -151,13 +266,85 @@ StackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { return false; } +/// ColorSlotsWithFreeRegs - If there are any free registers available, try +/// replacing spill slots references with registers instead. +bool +StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector &SlotMapping, + SmallVector, 16> &RevMap, + BitVector &SlotIsReg) { + if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters()) + return false; + + bool Changed = false; + DEBUG(dbgs() << "Assigning unused registers to spill slots:\n"); + for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { + LiveInterval *li = SSIntervals[i]; + int SS = li->getStackSlotIndex(); + if (!UsedColors[SS] || li->weight < 20) + // If the weight is < 20, i.e. two references in a loop with depth 1, + // don't bother with it. + continue; + + // These slots allow to share the same registers. + bool AllColored = true; + SmallVector ColoredRegs; + for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { + int RSS = RevMap[SS][j]; + const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS); + // If it's not colored to another stack slot, try coloring it + // to a "free" register. + if (!RC) { + AllColored = false; + continue; + } + unsigned Reg = VRM->getFirstUnusedRegister(RC); + if (!Reg) { + AllColored = false; + continue; + } + if (!AllMemRefsCanBeUnfolded(RSS)) { + AllColored = false; + continue; + } else { + DEBUG(dbgs() << "Assigning fi#" << RSS << " to " + << TRI->getName(Reg) << '\n'); + ColoredRegs.push_back(Reg); + SlotMapping[RSS] = Reg; + SlotIsReg.set(RSS); + Changed = true; + } + } + + // Register and its sub-registers are no longer free. + while (!ColoredRegs.empty()) { + unsigned Reg = ColoredRegs.back(); + ColoredRegs.pop_back(); + VRM->setRegisterUsed(Reg); + // If reg is a callee-saved register, it will have to be spilled in + // the prologue. + MRI->setPhysRegUsed(Reg); + for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { + VRM->setRegisterUsed(*AS); + MRI->setPhysRegUsed(*AS); + } + } + // This spill slot is dead after the rewrites + if (AllColored) { + MFI->RemoveStackObject(SS); + ++NumEliminated; + } + } + DEBUG(dbgs() << '\n'); + + return Changed; +} + /// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. /// int StackSlotColoring::ColorSlot(LiveInterval *li) { int Color = -1; bool Share = false; - if (!DisableSharing && - (DeleteLimit == -1 || (int)NumEliminated < DeleteLimit)) { + if (!DisableSharing) { // Check if it's possible to reuse any of the used colors. Color = UsedColors.find_first(); while (Color != -1) { @@ -182,7 +369,7 @@ 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"; + 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 @@ -200,46 +387,71 @@ int StackSlotColoring::ColorSlot(LiveInterval *li) { /// operands in the function. bool StackSlotColoring::ColorSlots(MachineFunction &MF) { unsigned NumObjs = MFI->getObjectIndexEnd(); - std::vector SlotMapping(NumObjs, -1); - SlotMapping.resize(NumObjs, -1); + SmallVector SlotMapping(NumObjs, -1); + SmallVector SlotWeights(NumObjs, 0.0); + SmallVector, 16> RevMap(NumObjs); + BitVector SlotIsReg(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 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 = li->getStackSlotIndex(); + 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 + + // Can we "color" a stack slot with a unused register? + Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg); + 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) { - 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); + SmallVector, 4> NewDefs(MF.getNumBlockIDs()); + for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { + bool isReg = SlotIsReg[SS]; + int NewFI = SlotMapping[SS]; + if (NewFI == -1 || (NewFI == (int)SS && !isReg)) + continue; + + const TargetRegisterClass *RC = LS->getIntervalRegClass(SS); + SmallVector &RefMIs = SSRefs[SS]; + for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) + if (!isReg) + RewriteInstruction(RefMIs[i], SS, NewFI, MF); + else { + // Rewrite to use a register instead. + unsigned MBBId = RefMIs[i]->getParent()->getNumber(); + SmallSet &Defs = NewDefs[MBBId]; + UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, Defs, MF); } - } } // 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); } @@ -247,18 +459,320 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { return true; } +/// AllMemRefsCanBeUnfolded - Return true if all references of the specified +/// spill slot index can be unfolded. +bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { + SmallVector &RefMIs = SSRefs[SS]; + for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) { + MachineInstr *MI = RefMIs[i]; + if (TII->isLoadFromStackSlot(MI, SS) || + TII->isStoreToStackSlot(MI, SS)) + // Restore and spill will become copies. + return true; + if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false)) + return false; + for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { + MachineOperand &MO = MI->getOperand(j); + if (MO.isFI() && MO.getIndex() != SS) + // If it uses another frameindex, we can, currently* unfold it. + return false; + } + } + return true; +} + +/// RewriteInstruction - Rewrite specified instruction by replacing references +/// to old frame index with new one. +void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, + int NewFI, 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 FI = MO.getIndex(); + if (FI != OldFI) + continue; + MO.setIndex(NewFI); + } + + // Update the memory references. This changes the MachineMemOperands + // directly. They may be in use by multiple instructions, however all + // instructions using OldFI are being rewritten to use NewFI. + const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); + const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI); + for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), + E = MI->memoperands_end(); I != E; ++I) + if ((*I)->getValue() == OldSV) + (*I)->setValue(NewSV); +} + +/// PropagateBackward - Traverse backward and look for the definition of +/// OldReg. If it can successfully update all of the references with NewReg, +/// do so and return true. +bool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII, + MachineBasicBlock *MBB, + unsigned OldReg, unsigned NewReg) { + if (MII == MBB->begin()) + return false; + + SmallVector Uses; + SmallVector Refs; + while (--MII != MBB->begin()) { + bool FoundDef = false; // Not counting 2address def. + + Uses.clear(); + const TargetInstrDesc &TID = MII->getDesc(); + for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MII->getOperand(i); + if (!MO.isReg()) + continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) + continue; + if (Reg == OldReg) { + if (MO.isImplicit()) + return false; + + // Abort the use is actually a sub-register def. We don't have enough + // information to figure out if it is really legal. + if (MO.getSubReg() || MII->isExtractSubreg() || + MII->isInsertSubreg() || MII->isSubregToReg()) + return false; + + const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI); + if (RC && !RC->contains(NewReg)) + return false; + + if (MO.isUse()) { + Uses.push_back(&MO); + } else { + Refs.push_back(&MO); + if (!MII->isRegTiedToUseOperand(i)) + FoundDef = true; + } + } else if (TRI->regsOverlap(Reg, NewReg)) { + return false; + } else if (TRI->regsOverlap(Reg, OldReg)) { + if (!MO.isUse() || !MO.isKill()) + return false; + } + } + + if (FoundDef) { + // Found non-two-address def. Stop here. + for (unsigned i = 0, e = Refs.size(); i != e; ++i) + Refs[i]->setReg(NewReg); + return true; + } + + // Two-address uses must be updated as well. + for (unsigned i = 0, e = Uses.size(); i != e; ++i) + Refs.push_back(Uses[i]); + } + return false; +} + +/// PropagateForward - Traverse forward and look for the kill of OldReg. If +/// it can successfully update all of the uses with NewReg, do so and +/// return true. +bool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII, + MachineBasicBlock *MBB, + unsigned OldReg, unsigned NewReg) { + if (MII == MBB->end()) + return false; + + SmallVector Uses; + while (++MII != MBB->end()) { + bool FoundKill = false; + const TargetInstrDesc &TID = MII->getDesc(); + for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MII->getOperand(i); + if (!MO.isReg()) + continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) + continue; + if (Reg == OldReg) { + if (MO.isDef() || MO.isImplicit()) + return false; + + // Abort the use is actually a sub-register use. We don't have enough + // information to figure out if it is really legal. + if (MO.getSubReg() || MII->isExtractSubreg()) + return false; + + const TargetRegisterClass *RC = TID.OpInfo[i].getRegClass(TRI); + if (RC && !RC->contains(NewReg)) + return false; + if (MO.isKill()) + FoundKill = true; + + Uses.push_back(&MO); + } else if (TRI->regsOverlap(Reg, NewReg) || + TRI->regsOverlap(Reg, OldReg)) + return false; + } + if (FoundKill) { + for (unsigned i = 0, e = Uses.size(); i != e; ++i) + Uses[i]->setReg(NewReg); + return true; + } + } + return false; +} + +/// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding +/// folded memory references and replacing those references with register +/// references instead. +void +StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, + unsigned Reg, + const TargetRegisterClass *RC, + SmallSet &Defs, + MachineFunction &MF) { + MachineBasicBlock *MBB = MI->getParent(); + if (unsigned DstReg = TII->isLoadFromStackSlot(MI, OldFI)) { + if (PropagateForward(MI, MBB, DstReg, Reg)) { + DEBUG(dbgs() << "Eliminated load: "); + DEBUG(MI->dump()); + ++NumLoadElim; + } else { + TII->copyRegToReg(*MBB, MI, DstReg, Reg, RC, RC, + MI->getDebugLoc()); + ++NumRegRepl; + } + + if (!Defs.count(Reg)) { + // If this is the first use of Reg in this MBB and it wasn't previously + // defined in MBB, add it to livein. + MBB->addLiveIn(Reg); + Defs.insert(Reg); + } + } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) { + if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) { + DEBUG(dbgs() << "Eliminated store: "); + DEBUG(MI->dump()); + ++NumStoreElim; + } else { + TII->copyRegToReg(*MBB, MI, Reg, SrcReg, RC, RC, + MI->getDebugLoc()); + ++NumRegRepl; + } + + // Remember reg has been defined in MBB. + Defs.insert(Reg); + } else { + SmallVector NewMIs; + bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs); + Success = Success; // Silence compiler warning. + assert(Success && "Failed to unfold!"); + MachineInstr *NewMI = NewMIs[0]; + MBB->insert(MI, NewMI); + ++NumRegRepl; + + if (NewMI->readsRegister(Reg)) { + if (!Defs.count(Reg)) + // If this is the first use of Reg in this MBB and it wasn't previously + // defined in MBB, add it to livein. + MBB->addLiveIn(Reg); + Defs.insert(Reg); + } + } + MBB->erase(MI); +} + +/// 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; + + MachineBasicBlock::iterator NextMI = llvm::next(I); + if (NextMI == MBB->end()) continue; + + int FirstSS, SecondSS; + 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 (SmallVector::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.getFunction()->getName() << '\n'; + }); MFI = MF.getFrameInfo(); + MRI = &MF.getRegInfo(); + TII = MF.getTarget().getInstrInfo(); + TRI = MF.getTarget().getRegisterInfo(); LS = &getAnalysis(); + VRM = &getAnalysis(); + loopInfo = &getAnalysis(); bool Changed = false; - if (InitializeSlots()) - Changed = ColorSlots(MF); + + unsigned NumSlots = LS->getNumIntervals(); + if (NumSlots < 2) { + if (NumSlots == 0 || !VRM->HasUnusedRegisters()) + // 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 + // .) + // + // FIXME: This goes beyond the setjmp/sigsetjmp functions. Ideally, we should + // check for the GCC "returns twice" attribute. + if (CheckForSetJmpCall(MF)) + 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(); @@ -267,5 +781,10 @@ bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { Assignments[i].clear(); Assignments.clear(); + if (Changed) { + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) + Changed |= RemoveDeadStores(I); + } + return Changed; }