X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=23ec84531e38a99bad0f044cfb9673a4a413056f;hb=3d878d80d67452865e286069ceefe918c0f65acb;hp=fbee19c07db7576ad7b888c106d522300a8308cb;hpb=64667b6418786edd2fceb022b3da0d3ad38221c2;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index fbee19c07db..23ec84531e3 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -44,9 +44,26 @@ 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 array is effectively a map, containing entries for // each physical register that currently has a value (ie, it is in @@ -263,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); @@ -301,7 +319,7 @@ void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { // 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 } @@ -371,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... @@ -453,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); @@ -495,7 +512,7 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { // 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 @@ -522,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) { @@ -540,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 } } @@ -562,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 } } @@ -579,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 } @@ -600,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) { @@ -631,12 +640,15 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) { else removePhysReg(i); - 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?"); +#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 @@ -655,6 +667,11 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { 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(); @@ -665,6 +682,7 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) { StackSlotForVirtReg.clear(); VirtRegModified.clear(); + Virt2PhysRegMap.clear(); return true; }