X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStackSlotColoring.cpp;h=8043556349808b18b78c801d88d1488b6548f3db;hb=174e597d466547d34cf8fcd2a95976e0cf5ebbac;hp=dd36bdd6041e870a0d7ab398696232435f4bcda0;hpb=fe095f39e7009c51d1c86769792ccbcad8cdd2ec;p=oota-llvm.git diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index dd36bdd6041..80435563498 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -13,19 +13,22 @@ #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/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 @@ -37,19 +40,22 @@ DisableSharing("no-stack-slot-sharing", cl::desc("Suppress slot sharing during stack coloring")); static cl::opt -ColorWithRegs("color-ss-with-regs", - cl::init(false), cl::Hidden, - cl::desc("Color stack slots with free registers")); +ColorWithRegsOpt("color-ss-with-regs", + cl::init(false), cl::Hidden, + cl::desc("Color stack slots with free registers")); static cl::opt DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); -STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); 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; @@ -87,9 +93,15 @@ namespace { public: static char ID; // Pass identification - StackSlotColoring() : MachineFunctionPass(&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(); @@ -106,6 +118,7 @@ namespace { private: void InitializeSlots(); + bool CheckForSetJmpCall(const MachineFunction &MF) const; void ScanForSpillSlotRefs(MachineFunction &MF); bool OverlapWithAssignments(LiveInterval *li, int Color) const; int ColorSlot(LiveInterval *li); @@ -115,8 +128,16 @@ namespace { 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, MachineFunction &MF); + unsigned Reg, const TargetRegisterClass *RC, + SmallSet &Defs, + MachineFunction &MF); bool AllMemRefsCanBeUnfolded(int SS); bool RemoveDeadStores(MachineBasicBlock* MBB); }; @@ -127,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 { @@ -141,6 +162,34 @@ namespace { }; } +/// 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) { @@ -164,7 +213,8 @@ void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { if (!LS->hasInterval(FI)) continue; LiveInterval &li = LS->getInterval(FI); - li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); + if (!MI->isDebugValue()) + li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); SSRefs[FI].push_back(MI); } } @@ -182,7 +232,7 @@ void StackSlotColoring::InitializeSlots() { Assignments.resize(LastFI); // Gather all spill slots into a list. - DOUT << "Spill slot intervals:\n"; + 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()); @@ -194,7 +244,7 @@ void StackSlotColoring::InitializeSlots() { OrigSizes[FI] = MFI->getObjectSize(FI); AllColors.set(FI); } - DOUT << '\n'; + DEBUG(dbgs() << '\n'); // Sort them by weight. std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); @@ -222,15 +272,17 @@ bool StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector &SlotMapping, SmallVector, 16> &RevMap, BitVector &SlotIsReg) { - if (!ColorWithRegs || !VRM->HasUnusedRegisters()) + if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters()) return false; bool Changed = false; - DOUT << "Assigning unused registers to spill slots:\n"; + 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]) + 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. @@ -254,7 +306,8 @@ StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector &SlotMapping, AllColored = false; continue; } else { - DOUT << "Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n'; + DEBUG(dbgs() << "Assigning fi#" << RSS << " to " + << TRI->getName(Reg) << '\n'); ColoredRegs.push_back(Reg); SlotMapping[RSS] = Reg; SlotIsReg.set(RSS); @@ -281,7 +334,7 @@ StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector &SlotMapping, ++NumEliminated; } } - DOUT << '\n'; + DEBUG(dbgs() << '\n'); return Changed; } @@ -316,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 @@ -340,7 +393,7 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { BitVector SlotIsReg(NumObjs); BitVector UsedColors(NumObjs); - DOUT << "Color spill slot intervals:\n"; + DEBUG(dbgs() << "Color spill slot intervals:\n"); bool Changed = false; for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { LiveInterval *li = SSIntervals[i]; @@ -354,7 +407,7 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { Changed |= (SS != NewSS); } - DOUT << "\nSpill slots after coloring:\n"; + 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(); @@ -366,7 +419,7 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { #ifndef NDEBUG for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) DEBUG(SSIntervals[i]->dump()); - DOUT << '\n'; + DEBUG(dbgs() << '\n'); #endif // Can we "color" a stack slot with a unused register? @@ -376,24 +429,29 @@ bool StackSlotColoring::ColorSlots(MachineFunction &MF) { return false; // Rewrite all MO_FrameIndex operands. + 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) - // Rewrite to use a register instead. - UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, MF); - else + 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); } @@ -407,6 +465,10 @@ 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) { @@ -423,6 +485,7 @@ bool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { /// 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()) @@ -433,37 +496,190 @@ void StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, 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); + // 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); - for (unsigned i = 0, ee = MMOs.size(); i != ee; ++i) { - if (MMOs[i].getValue() != OldSV) - MI->addMemOperand(MF, MMOs[i]); - else { - MachineMemOperand MMO(PseudoSourceValue::getFixedStack(NewFI), - MMOs[i].getFlags(), MMOs[i].getOffset(), - MMOs[i].getSize(), MMOs[i].getAlignment()); - MI->addMemOperand(MF, MMO); + 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, - MachineFunction &MF) { +void +StackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, + unsigned Reg, + const TargetRegisterClass *RC, + SmallSet &Defs, + MachineFunction &MF) { MachineBasicBlock *MBB = MI->getParent(); - SmallVector NewMIs; - bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs); - assert(Success && "Failed to unfold!"); - MBB->insert(MI, NewMIs[0]); + 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); - ++NumRegRepl; } /// RemoveDeadStores - Scan through a basic block and look for loads followed @@ -483,7 +699,7 @@ bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { if (DCELimit != -1 && (int)NumDead >= DCELimit) break; - MachineBasicBlock::iterator NextMI = next(I); + MachineBasicBlock::iterator NextMI = llvm::next(I); if (NextMI == MBB->end()) continue; int FirstSS, SecondSS; @@ -514,7 +730,11 @@ bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { 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(); @@ -533,6 +753,16 @@ bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 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();