X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=23ec84531e38a99bad0f044cfb9673a4a413056f;hb=3d878d80d67452865e286069ceefe918c0f65acb;hp=680bda7cdca637d746d2d4887460b8db90a3cf39;hpb=ef09c63e7ba5dd5410655f71d35eb7245893b1f1;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index 680bda7cdca..23ec84531e3 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -44,17 +44,36 @@ namespace { std::map StackSlotForVirtReg; // Virt2PhysRegMap - This map contains entries for each virtual register - // that is currently available in a physical 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::map Virt2PhysRegMap; + std::vector Virt2PhysRegMap; + + unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { + assert(VirtReg >= MRegisterInfo::FirstVirtualRegister &&"Illegal VREG #"); + assert(VirtReg-MRegisterInfo::FirstVirtualRegister = MRegisterInfo::FirstVirtualRegister &&"Illegal VREG #"); + if (VirtReg-MRegisterInfo::FirstVirtualRegister >= Virt2PhysRegMap.size()) + Virt2PhysRegMap.resize(VirtReg-MRegisterInfo::FirstVirtualRegister+1); + return Virt2PhysRegMap[VirtReg-MRegisterInfo::FirstVirtualRegister]; + } - // PhysRegsUsed - This map contains entries for each physical register that - // currently has a value (ie, it is in Virt2PhysRegMap). The value mapped - // to is the virtual register corresponding to the physical register (the - // inverse of the Virt2PhysRegMap), or 0. The value is set to 0 if this - // register is pinned because it is used by a future instruction. + // PhysRegsUsed - This array is effectively a map, containing entries for + // each physical register that currently has a value (ie, it is in + // Virt2PhysRegMap). The value mapped to is the virtual register + // corresponding to the physical register (the inverse of the + // Virt2PhysRegMap), or 0. The value is set to 0 if this register is pinned + // because it is used by a future instruction. If the entry for a physical + // register is -1, then the physical register is "not in the map". // - std::map PhysRegsUsed; + int PhysRegsUsed[MRegisterInfo::FirstVirtualRegister]; // PhysRegsUseOrder - This contains a list of the physical registers that // currently have a virtual register value in them. This list provides an @@ -227,7 +246,7 @@ int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { /// longer being in use. /// void RA::removePhysReg(unsigned PhysReg) { - PhysRegsUsed.erase(PhysReg); // PhyReg no longer used + PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used std::vector::iterator It = std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg); @@ -261,7 +280,8 @@ void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); ++NumSpilled; // Update statistics } - Virt2PhysRegMap.erase(VirtReg); // VirtReg no longer available + + getVirt2PhysRegMapSlot(VirtReg) = 0; // VirtReg no longer available DEBUG(std::cerr << "\n"); removePhysReg(PhysReg); @@ -275,20 +295,17 @@ void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, /// void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, unsigned PhysReg, bool OnlyVirtRegs) { - std::map::iterator PI = PhysRegsUsed.find(PhysReg); - if (PI != PhysRegsUsed.end()) { // Only spill it if it's used! - if (PI->second || !OnlyVirtRegs) - spillVirtReg(MBB, I, PI->second, PhysReg); + if (PhysRegsUsed[PhysReg] != -1) { // Only spill it if it's used! + if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs) + spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg); } else { // If the selected register aliases any other registers, we must make // sure that one of the aliases isn't alive... for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); - *AliasSet; ++AliasSet) { - PI = PhysRegsUsed.find(*AliasSet); - if (PI != PhysRegsUsed.end()) // Spill aliased register... - if (PI->second || !OnlyVirtRegs) - spillVirtReg(MBB, I, PI->second, *AliasSet); - } + *AliasSet; ++AliasSet) + if (PhysRegsUsed[*AliasSet] != -1) // Spill aliased register... + if (PhysRegsUsed[*AliasSet] || !OnlyVirtRegs) + spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); } } @@ -298,12 +315,11 @@ void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, /// register must not be used for anything else when this is called. /// void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { - assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() && - "Phys reg already assigned!"); + assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!"); // Update information to note the fact that this register was just used, and // it holds VirtReg. PhysRegsUsed[PhysReg] = VirtReg; - Virt2PhysRegMap[VirtReg] = PhysReg; + getOrInsertVirt2PhysRegMapSlot(VirtReg) = PhysReg; PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg } @@ -313,13 +329,13 @@ void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { /// registers are all free... /// bool RA::isPhysRegAvailable(unsigned PhysReg) const { - if (PhysRegsUsed.count(PhysReg)) return false; + if (PhysRegsUsed[PhysReg] != -1) return false; // If the selected register aliases any other allocated registers, it is // not free! for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); *AliasSet; ++AliasSet) - if (PhysRegsUsed.count(*AliasSet)) // Aliased register in use? + if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use? return false; // Can't use this reg then. return true; } @@ -359,9 +375,9 @@ void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, // 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. - std::map::iterator PRUI = PhysRegsUsed.find(PhysReg); - if (PRUI != PhysRegsUsed.end()) { - unsigned VirtReg = PRUI->second; // The virtual register held... + 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... @@ -373,7 +389,7 @@ void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, // Update our internal state to indicate that PhysReg is available and Reg // isn't. - Virt2PhysRegMap.erase(VirtReg); + getVirt2PhysRegMapSlot[VirtReg] = 0; removePhysReg(PhysReg); // Free the physreg // Move reference over to new register... @@ -413,7 +429,7 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, // We can only use this register if it holds a virtual register (ie, it // can be spilled). Do not use it if it is an explicitly allocated // physical register! - assert(PhysRegsUsed.count(R) && + assert(PhysRegsUsed[R] != -1 && "PhysReg in PhysRegsUseOrder, but is not allocated?"); if (PhysRegsUsed[R]) { // If the current register is compatible, use it. @@ -455,10 +471,9 @@ unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, unsigned RA::reloadVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, unsigned VirtReg) { - std::map::iterator It = Virt2PhysRegMap.find(VirtReg); - if (It != Virt2PhysRegMap.end()) { - MarkPhysRegRecentlyUsed(It->second); - return It->second; // Already have this value available! + if (unsigned PR = getOrInsertVirt2PhysRegMapSlot(VirtReg)) { + MarkPhysRegRecentlyUsed(PR); + return PR; // Already have this value available! } unsigned PhysReg = getReg(MBB, I, VirtReg); @@ -487,17 +502,17 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode()); DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI; std::cerr << " Regs have values: "; - for (std::map::const_iterator - I = PhysRegsUsed.begin(), E = PhysRegsUsed.end(); I != E; ++I) - std::cerr << "[" << RegInfo->getName(I->first) - << ",%reg" << I->second << "] "; + for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) + if (PhysRegsUsed[i] != -1) + std::cerr << "[" << RegInfo->getName(i) + << ",%reg" << PhysRegsUsed[i] << "] "; std::cerr << "\n"); // Loop over the implicit uses, making sure that they are at the head of the // use order list, so they don't get reallocated. for (const unsigned *ImplicitUses = TID.ImplicitUses; *ImplicitUses; ++ImplicitUses) - MarkPhysRegRecentlyUsed(*ImplicitUses); + MarkPhysRegRecentlyUsed(*ImplicitUses); // Get the used operands into registers. This has the potential to spill // incoming values if we are out of registers. Note that we completely @@ -524,11 +539,10 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { unsigned VirtReg = KI->second; unsigned PhysReg = VirtReg; if (MRegisterInfo::isVirtualRegister(VirtReg)) { - std::map::iterator I = - Virt2PhysRegMap.find(VirtReg); - assert(I != Virt2PhysRegMap.end()); - PhysReg = I->second; - Virt2PhysRegMap.erase(I); + unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); + PhysReg = PhysRegSlot; + assert(PhysReg != 0); + PhysRegSlot = 0; } if (PhysReg) { @@ -542,16 +556,16 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // 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).isPhysicalRegister()) { + if (MI->getOperand(i).isDef() && MI->getOperand(i).isRegister() && + MRegisterInfo::isPhysicalRegister(MI->getOperand(i).getReg())) { unsigned Reg = MI->getOperand(i).getAllocatedRegNum(); spillPhysReg(MBB, I, Reg, true); // Spill any existing value in the reg PhysRegsUsed[Reg] = 0; // It is free and reserved now PhysRegsUseOrder.push_back(Reg); for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); *AliasSet; ++AliasSet) { - PhysRegsUseOrder.push_back(*AliasSet); - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + PhysRegsUseOrder.push_back(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now } } @@ -564,8 +578,8 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { PhysRegsUsed[Reg] = 0; // It is free and reserved now for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); *AliasSet; ++AliasSet) { - PhysRegsUseOrder.push_back(*AliasSet); - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + PhysRegsUseOrder.push_back(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now } } @@ -581,14 +595,8 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { unsigned DestPhysReg; // If DestVirtReg already has a value, use it. - std::map::iterator DestI = - Virt2PhysRegMap.find(DestVirtReg); - if (DestI != Virt2PhysRegMap.end()) { - DestPhysReg = DestI->second; - } - else { + if (!(DestPhysReg = getOrInsertVirt2PhysRegMapSlot(DestVirtReg))) DestPhysReg = getReg(MBB, I, DestVirtReg); - } markVirtRegModified(DestVirtReg); MI->SetMachineOperandReg(i, DestPhysReg); // Assign the output register } @@ -602,11 +610,10 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { unsigned VirtReg = KI->second; unsigned PhysReg = VirtReg; if (MRegisterInfo::isVirtualRegister(VirtReg)) { - std::map::iterator I = - Virt2PhysRegMap.find(VirtReg); - assert(I != Virt2PhysRegMap.end()); - PhysReg = I->second; - Virt2PhysRegMap.erase(I); + unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); + PhysReg = PhysRegSlot; + assert(PhysReg != 0); + PhysRegSlot = 0; } if (PhysReg) { @@ -626,18 +633,22 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { --I; // Spill all physical registers holding virtual registers now. - while (!PhysRegsUsed.empty()) - if (unsigned VirtReg = PhysRegsUsed.begin()->second) - spillVirtReg(MBB, I, VirtReg, PhysRegsUsed.begin()->first); - else - removePhysReg(PhysRegsUsed.begin()->first); - - for (std::map::iterator I = Virt2PhysRegMap.begin(), - E = Virt2PhysRegMap.end(); I != E; ++I) - std::cerr << "Register still mapped: " << I->first << " -> " - << I->second << "\n"; - - assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?"); + for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) + if (PhysRegsUsed[i] != -1) + if (unsigned VirtReg = PhysRegsUsed[i]) + spillVirtReg(MBB, I, VirtReg, i); + else + removePhysReg(i); + +#ifndef NDEBUG + bool AllOk = true; + for (unsigned i = 0, e = Virt2PhysRegMap.size(); i != e; ++i) + if (unsigned PR = Virt2PhysRegMap[i]) { + std::cerr << "Register still mapped: " << i << " -> " << PR << "\n"; + AllOk = false; + } + assert(AllOk && "Virtual registers still in phys regs?"); +#endif // Clear any physical register which appear live at the end of the basic // block, but which do not hold any virtual registers. e.g., the stack @@ -654,6 +665,13 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { TM = &Fn.getTarget(); RegInfo = TM->getRegisterInfo(); + memset(PhysRegsUsed, -1, RegInfo->getNumRegs()*sizeof(unsigned)); + + // Reserve some space for a moderate number of registers. If we know what the + // max virtual register number was we could use that instead and save some + // runtime overhead... + Virt2PhysRegMap.resize(1024); + if (!DisableKill) LV = &getAnalysis(); @@ -664,6 +682,7 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { StackSlotForVirtReg.clear(); VirtRegModified.clear(); + Virt2PhysRegMap.clear(); return true; }