X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStackSlotColoring.cpp;h=12d38f0a76d0f5d6c6fab016047688301eeff2a5;hb=f91387847421a1f0914e757cca96a4d213d32890;hp=139d12b4edd4f4b1a0cd000a1a27f0c665fd1c93;hpb=c781a243a3d17e7e763515794168d8fa6043f565;p=oota-llvm.git diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp index 139d12b4edd..12d38f0a76d 100644 --- a/lib/CodeGen/StackSlotColoring.cpp +++ b/lib/CodeGen/StackSlotColoring.cpp @@ -18,14 +18,15 @@ #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 +38,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 +91,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(); @@ -115,8 +125,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 +145,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 { @@ -182,7 +200,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 +212,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,73 +240,69 @@ 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; - // Get the largest common sub- register class of all the stack slots that - // are colored to this stack slot. - const TargetRegisterClass *RC = 0; - for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { - int RSS = RevMap[SS][j]; - const TargetRegisterClass *RRC = LS->getIntervalRegClass(RSS); - if (!RC) - RC = RRC; - else - RC = getCommonSubClass(RC, RRC); - } - // If it's not colored to another stack slot, try coloring it - // to a "free" register. - if (!RC) - continue; - unsigned Reg = VRM->getFirstUnusedRegister(RC); - if (!Reg) - continue; - bool IsSafe = true; + // 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)) { - IsSafe = false; - break; + 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; } } - if (!IsSafe) - // Try color the next spill slot. - continue; - DOUT << "Assigning fi#" << SS << " to " << TRI->getName(Reg) - << ", which in turn means...\n"; // Register and its sub-registers are no longer free. - 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); + 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 - MFI->RemoveStackObject(SS); - - // Remember all these FI references will have to be unfolded. - for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { - int RSS = RevMap[SS][j]; - DOUT << " Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n'; - SlotMapping[RSS] = Reg; - SlotIsReg.set(RSS); + if (AllColored) { + MFI->RemoveStackObject(SS); + ++NumEliminated; } - - ++NumEliminated; - Changed = true; } - DOUT << '\n'; + DEBUG(dbgs() << '\n'); return Changed; } @@ -323,7 +337,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 @@ -347,7 +361,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]; @@ -361,7 +375,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(); @@ -373,7 +387,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? @@ -383,24 +397,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); } @@ -414,6 +433,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) { @@ -430,6 +453,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()) @@ -440,37 +464,188 @@ 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); + ++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); + ++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 @@ -490,7 +665,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; @@ -521,7 +696,7 @@ bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { bool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { - DOUT << "********** Stack Slot Coloring **********\n"; + DEBUG(dbgs() << "********** Stack Slot Coloring **********\n"); MFI = MF.getFrameInfo(); MRI = &MF.getRegInfo();