X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=d3c3277cbbf35cbcc1fc0b63b6a4d1ad789dee18;hb=ef9531efedd2233269f670227fb0e6aae7480d53;hp=59bb1a542b6417a27325a5b92d579aa0d01cd305;hpb=11390e76e73d36e62c981069a67d1d33823262de;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index 59bb1a542b6..d3c3277cbbf 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -21,43 +21,35 @@ #include "llvm/CodeGen/LiveVariables.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "Support/CommandLine.h" -#include "Support/Debug.h" -#include "Support/Statistic.h" -#include +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Statistic.h" +#include using namespace llvm; namespace { - Statistic<> NumSpilled ("ra-local", "Number of registers spilled"); - Statistic<> NumReloaded("ra-local", "Number of registers reloaded"); - Statistic<> NumFused ("ra-local", "Number of reloads fused into instructions"); - cl::opt DisableKill("disable-kill", cl::Hidden, - cl::desc("Disable register kill in local-ra")); - + Statistic<> NumStores("ra-local", "Number of stores added"); + Statistic<> NumLoads ("ra-local", "Number of loads added"); + Statistic<> NumFolded("ra-local", "Number of loads/stores folded into " + "instructions"); class RA : public MachineFunctionPass { const TargetMachine *TM; MachineFunction *MF; const MRegisterInfo *RegInfo; LiveVariables *LV; + bool *PhysRegsEverUsed; // StackSlotForVirtReg - Maps virtual regs to the frame index where these // values are spilled. std::map StackSlotForVirtReg; // Virt2PhysRegMap - This map contains entries for each virtual register - // that is currently available in a physical register. This is "logically" - // a map from virtual register numbers to physical register numbers. - // Instead of using a map, however, which is slow, we use a vector. The - // index is the VREG number - FirstVirtualRegister. If the entry is zero, - // then it is logically "not in the map". - // - std::vector Virt2PhysRegMap; + // that is currently available in a physical register. + DenseMap Virt2PhysRegMap; unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { - assert(MRegisterInfo::isVirtualRegister(VirtReg) &&"Illegal VREG #"); - assert(VirtReg-MRegisterInfo::FirstVirtualRegister (); + AU.addRequired(); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); @@ -163,7 +154,7 @@ namespace { /// the virtual register slot specified by VirtReg. It then updates the RA /// data structures to indicate the fact that PhysReg is now available. /// - void spillVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, + void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, unsigned VirtReg, unsigned PhysReg); /// spillPhysReg - This method spills the specified physical register into @@ -236,7 +227,8 @@ int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { return I->second; // Already has space allocated? // Allocate a new stack object for this spill location... - int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC); + int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), + RC->getAlignment()); // Assign the slot... StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx)); @@ -261,9 +253,8 @@ void RA::removePhysReg(unsigned PhysReg) { /// virtual register slot specified by VirtReg. It then updates the RA data /// structures to indicate the fact that PhysReg is now available. /// -void RA::spillVirtReg(MachineBasicBlock &MBB, MachineInstr *I, +void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I, unsigned VirtReg, unsigned PhysReg) { - if (!VirtReg && DisableKill) return; assert(VirtReg && "Spilling a physical register is illegal!" " Must not have appropriate kill for the register or use exists beyond" " the intended one."); @@ -279,8 +270,8 @@ void RA::spillVirtReg(MachineBasicBlock &MBB, MachineInstr *I, const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); DEBUG(std::cerr << " to stack slot #" << FrameIndex); - RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); - ++NumSpilled; // Update statistics + RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex); + ++NumStores; // Update statistics } getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available @@ -367,39 +358,6 @@ unsigned RA::getFreeReg(const TargetRegisterClass *RC) { /// void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, unsigned PhysReg) { - // FIXME: This code checks to see if a register is available, but it really - // wants to know if a reg is available BEFORE the instruction executes. If - // called after killed operands are freed, it runs the risk of reallocating a - // used operand... -#if 0 - if (isPhysRegAvailable(PhysReg)) return; // Already available... - - // Check to see if the register is directly used, not indirectly used through - // aliases. If aliased registers are the ones actually used, we cannot be - // sure that we will be able to save the whole thing if we do a reg-reg copy. - if (PhysRegsUsed[PhysReg] != -1) { - // The virtual register held... - unsigned VirtReg = PhysRegsUsed[PhysReg]->second; - - // Check to see if there is a compatible register available. If so, we can - // move the value into the new register... - // - const TargetRegisterClass *RC = RegInfo->getRegClass(PhysReg); - if (unsigned NewReg = getFreeReg(RC)) { - // Emit the code to copy the value... - RegInfo->copyRegToReg(MBB, I, NewReg, PhysReg, RC); - - // Update our internal state to indicate that PhysReg is available and Reg - // isn't. - getVirt2PhysRegMapSlot[VirtReg] = 0; - removePhysReg(PhysReg); // Free the physreg - - // Move reference over to new register... - assignVirtToPhysReg(VirtReg, NewReg); - return; - } - } -#endif spillPhysReg(MBB, I, PhysReg); } @@ -435,7 +393,7 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineInstr *I, "PhysReg in PhysRegsUseOrder, but is not allocated?"); if (PhysRegsUsed[R]) { // If the current register is compatible, use it. - if (RegInfo->getRegClass(R) == RC) { + if (RC->contains(R)) { PhysReg = R; break; } else { @@ -443,7 +401,7 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineInstr *I, // compatible, use it. for (const unsigned *AliasSet = RegInfo->getAliasSet(R); *AliasSet; ++AliasSet) { - if (RegInfo->getRegClass(*AliasSet) == RC) { + if (RC->contains(*AliasSet)) { PhysReg = *AliasSet; // Take an aliased register break; } @@ -498,10 +456,12 @@ MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, assignVirtToPhysReg(VirtReg, PhysReg); } else { // No registers available. // If we can fold this spill into this instruction, do so now. - MachineBasicBlock::iterator MII = MI; - if (RegInfo->foldMemoryOperand(MII, OpNum, FrameIndex)) { - ++NumFused; - return MII; + if (MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)){ + ++NumFolded; + // Since we changed the address of MI, make sure to update live variables + // to know that the new instruction has the properties of the old one. + LV->instructionChanged(MI, FMI); + return MBB.insert(MBB.erase(MI), FMI); } // It looks like we can't fold this virtual register load into this @@ -516,9 +476,10 @@ MachineInstr *RA::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, << RegInfo->getName(PhysReg) << "\n"); // Add move instruction(s) - RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); - ++NumReloaded; // Update statistics + RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex); + ++NumLoads; // Update statistics + PhysRegsEverUsed[PhysReg] = true; MI->SetMachineOperandReg(OpNum, PhysReg); // Assign the input register return MI; } @@ -529,7 +490,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // loop over each instruction MachineBasicBlock::iterator MI = MBB.begin(); for (; MI != MBB.end(); ++MI) { - const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode()); + const TargetInstrDescriptor &TID = TM->getInstrInfo()->get(MI->getOpcode()); DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI; std::cerr << " Regs have values: "; for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) @@ -550,43 +511,45 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // physical register is referenced by the instruction, that it is guaranteed // to be live-in, or the input is badly hosed. // - for (unsigned i = 0; i != MI->getNumOperands(); ++i) - if (MI->getOperand(i).isUse() && - !MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() && - MRegisterInfo::isVirtualRegister(MI->getOperand(i).getReg())) + for (unsigned i = 0; i != MI->getNumOperands(); ++i) { + MachineOperand& MO = MI->getOperand(i); + // here we are looking for only used operands (never def&use) + if (!MO.isDef() && MO.isRegister() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) MI = reloadVirtReg(MBB, MI, i); + } - if (!DisableKill) { - // If this instruction is the last user of anything in registers, kill the - // value, freeing the register being used, so it doesn't need to be - // spilled to memory. - // - for (LiveVariables::killed_iterator KI = LV->killed_begin(MI), - KE = LV->killed_end(MI); KI != KE; ++KI) { - unsigned VirtReg = KI->second; - unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { - // If the virtual register was never materialized into a register, it - // might not be in the map, but it won't hurt to zero it out anyway. - unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); - PhysReg = PhysRegSlot; - PhysRegSlot = 0; - } + // If this instruction is the last user of anything in registers, kill the + // value, freeing the register being used, so it doesn't need to be + // spilled to memory. + // + for (LiveVariables::killed_iterator KI = LV->killed_begin(MI), + KE = LV->killed_end(MI); KI != KE; ++KI) { + unsigned VirtReg = KI->second; + unsigned PhysReg = VirtReg; + if (MRegisterInfo::isVirtualRegister(VirtReg)) { + // If the virtual register was never materialized into a register, it + // might not be in the map, but it won't hurt to zero it out anyway. + unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); + PhysReg = PhysRegSlot; + PhysRegSlot = 0; + } - if (PhysReg) { - DEBUG(std::cerr << " Last use of " << RegInfo->getName(PhysReg) - << "[%reg" << VirtReg <<"], removing it from live set\n"); - removePhysReg(PhysReg); - } + if (PhysReg) { + DEBUG(std::cerr << " Last use of " << RegInfo->getName(PhysReg) + << "[%reg" << VirtReg <<"], removing it from live set\n"); + removePhysReg(PhysReg); } } // Loop over all of the operands of the instruction, spilling registers that // are defined, and marking explicit destinations in the PhysRegsUsed map. - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) - if (MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() && - MRegisterInfo::isPhysicalRegister(MI->getOperand(i).getReg())) { - unsigned Reg = MI->getOperand(i).getReg(); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isDef() && MO.isRegister() && MO.getReg() && + MRegisterInfo::isPhysicalRegister(MO.getReg())) { + unsigned Reg = MO.getReg(); + PhysRegsEverUsed[Reg] = true; spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in the reg PhysRegsUsed[Reg] = 0; // It is free and reserved now PhysRegsUseOrder.push_back(Reg); @@ -594,8 +557,10 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { *AliasSet; ++AliasSet) { PhysRegsUseOrder.push_back(*AliasSet); PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + PhysRegsEverUsed[*AliasSet] = true; } } + } // Loop over the implicit defs, spilling them as well. for (const unsigned *ImplicitDefs = TID.ImplicitDefs; @@ -604,61 +569,61 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { spillPhysReg(MBB, MI, Reg, true); PhysRegsUseOrder.push_back(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now + PhysRegsEverUsed[Reg] = true; + for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); *AliasSet; ++AliasSet) { PhysRegsUseOrder.push_back(*AliasSet); PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + PhysRegsEverUsed[*AliasSet] = true; } } // Okay, we have allocated all of the source operands and spilled any values // that would be destroyed by defs of this instruction. Loop over the - // implicit defs and assign them to a register, spilling incoming values if + // explicit defs and assign them to a register, spilling incoming values if // we need to scavenge a register. // - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) - if (MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() && - MRegisterInfo::isVirtualRegister(MI->getOperand(i).getReg())) { - unsigned DestVirtReg = MI->getOperand(i).getReg(); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isDef() && MO.isRegister() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) { + unsigned DestVirtReg = MO.getReg(); unsigned DestPhysReg; // If DestVirtReg already has a value, use it. if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) DestPhysReg = getReg(MBB, MI, DestVirtReg); + PhysRegsEverUsed[DestPhysReg] = true; markVirtRegModified(DestVirtReg); MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register } + } - if (!DisableKill) { - // If this instruction defines any registers that are immediately dead, - // kill them now. - // - for (LiveVariables::killed_iterator KI = LV->dead_begin(MI), - KE = LV->dead_end(MI); KI != KE; ++KI) { - unsigned VirtReg = KI->second; - unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { - unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); - PhysReg = PhysRegSlot; - assert(PhysReg != 0); - PhysRegSlot = 0; - } + // If this instruction defines any registers that are immediately dead, + // kill them now. + // + for (LiveVariables::killed_iterator KI = LV->dead_begin(MI), + KE = LV->dead_end(MI); KI != KE; ++KI) { + unsigned VirtReg = KI->second; + unsigned PhysReg = VirtReg; + if (MRegisterInfo::isVirtualRegister(VirtReg)) { + unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); + PhysReg = PhysRegSlot; + assert(PhysReg != 0); + PhysRegSlot = 0; + } - if (PhysReg) { - DEBUG(std::cerr << " Register " << RegInfo->getName(PhysReg) - << " [%reg" << VirtReg - << "] is never used, removing it frame live list\n"); - removePhysReg(PhysReg); - } + if (PhysReg) { + DEBUG(std::cerr << " Register " << RegInfo->getName(PhysReg) + << " [%reg" << VirtReg + << "] is never used, removing it frame live list\n"); + removePhysReg(PhysReg); } } } - // Rewind the iterator to point to the first flow control instruction... - const TargetInstrInfo &TII = TM->getInstrInfo(); - MI = MBB.end(); - while (MI != MBB.begin() && TII.isTerminatorInstr((--MI)->getOpcode())); - ++MI; + MI = MBB.getFirstTerminator(); // Spill all physical registers holding virtual registers now. for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) @@ -670,7 +635,8 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { #ifndef NDEBUG bool AllOk = true; - for (unsigned i = 0, e = Virt2PhysRegMap.size(); i != e; ++i) + for (unsigned i = MRegisterInfo::FirstVirtualRegister, + e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i) if (unsigned PR = Virt2PhysRegMap[i]) { std::cerr << "Register still mapped: " << i << " -> " << PR << "\n"; AllOk = false; @@ -692,15 +658,17 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { MF = &Fn; TM = &Fn.getTarget(); RegInfo = TM->getRegisterInfo(); + LV = &getAnalysis(); + + PhysRegsEverUsed = new bool[RegInfo->getNumRegs()]; + std::fill(PhysRegsEverUsed, PhysRegsEverUsed+RegInfo->getNumRegs(), false); + Fn.setUsedPhysRegs(PhysRegsEverUsed); PhysRegsUsed.assign(RegInfo->getNumRegs(), -1); // initialize the virtual->physical register map to have a 'null' // mapping for all virtual registers - Virt2PhysRegMap.assign(MF->getSSARegMap()->getNumVirtualRegs(), 0); - - if (!DisableKill) - LV = &getAnalysis(); + Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg()); // Loop over all of the basic blocks, eliminating virtual register references for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();