X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLocal.cpp;h=59831f0b707aef295b27960b9dfe9d3648fead81;hb=990f032907ae171cc3d465a694e8e6d2a6545f57;hp=c933c51b3fcf8834203f1a213e3ac89a6ab3bc93;hpb=22ff3eeebeb4d17749ab9d5cd4d5807f3066bb94;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp index c933c51b3fc..59831f0b707 100644 --- a/lib/CodeGen/RegAllocLocal.cpp +++ b/lib/CodeGen/RegAllocLocal.cpp @@ -29,19 +29,19 @@ #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/STLExtras.h" #include +#include using namespace llvm; STATISTIC(NumStores, "Number of stores added"); STATISTIC(NumLoads , "Number of loads added"); -STATISTIC(NumFolded, "Number of loads/stores folded into instructions"); - -namespace { - static RegisterRegAlloc - localRegAlloc("local", " local register allocator", - createLocalRegisterAllocator); +static RegisterRegAlloc + localRegAlloc("local", " local register allocator", + createLocalRegisterAllocator); +namespace { class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass { public: static char ID; @@ -49,7 +49,7 @@ namespace { private: const TargetMachine *TM; MachineFunction *MF; - const MRegisterInfo *MRI; + const TargetRegisterInfo *TRI; const TargetInstrInfo *TII; // StackSlotForVirtReg - Maps virtual regs to the frame index where these @@ -91,7 +91,7 @@ namespace { Virt2LastUseMap; std::pair& getVirtRegLastUse(unsigned Reg) { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); return Virt2LastUseMap[Reg]; } @@ -103,8 +103,8 @@ namespace { BitVector VirtRegModified; void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - Reg -= MRegisterInfo::FirstVirtualRegister; + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + Reg -= TargetRegisterInfo::FirstVirtualRegister; if (Val) VirtRegModified.set(Reg); else @@ -112,10 +112,10 @@ namespace { } bool isVirtRegModified(unsigned Reg) const { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size() + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size() && "Illegal virtual register!"); - return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister]; + return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; } void AddToPhysRegsUseOrder(unsigned Reg) { @@ -167,7 +167,7 @@ namespace { /// bool areRegsEqual(unsigned R1, unsigned R2) const { if (R1 == R2) return true; - for (const unsigned *AliasSet = MRI->getAliasSet(R2); + for (const unsigned *AliasSet = TRI->getAliasSet(R2); *AliasSet; ++AliasSet) { if (*AliasSet == R1) return true; } @@ -286,7 +286,7 @@ void RALocal::spillVirtReg(MachineBasicBlock &MBB, assert(VirtReg && "Spilling a physical register is illegal!" " Must not have appropriate kill for the register or use exists beyond" " the intended one."); - DOUT << " Spilling register " << MRI->getName(PhysReg) + DOUT << " Spilling register " << TRI->getName(PhysReg) << " containing %reg" << VirtReg; const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); @@ -296,16 +296,18 @@ void RALocal::spillVirtReg(MachineBasicBlock &MBB, std::pair &LastUse = getVirtRegLastUse(VirtReg); if (LastUse.first) LastUse.first->getOperand(LastUse.second).setIsKill(); - } - - // Otherwise, there is a virtual register corresponding to this physical - // register. We only need to spill it into its stack slot if it has been - // modified. - if (isVirtRegModified(VirtReg)) { + } else { + // Otherwise, there is a virtual register corresponding to this physical + // register. We only need to spill it into its stack slot if it has been + // modified. const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); DOUT << " to stack slot #" << FrameIndex; - TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIndex, RC); + // If the instruction reads the register that's spilled, (e.g. this can + // happen if it is a move to a physical register), then the spill + // instruction is not a kill. + bool isKill = !(I != MBB.end() && I->readsRegister(PhysReg)); + TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC); ++NumStores; // Update statistics } @@ -330,7 +332,7 @@ void RALocal::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, } 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 = MRI->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) if (PhysRegsUsed[*AliasSet] != -1 && // Spill aliased register. PhysRegsUsed[*AliasSet] != -2) // If allocatable. @@ -363,9 +365,9 @@ bool RALocal::isPhysRegAvailable(unsigned PhysReg) const { // If the selected register aliases any other allocated registers, it is // not free! - for (const unsigned *AliasSet = MRI->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) - if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use? + if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use? return false; // Can't use this reg then. return true; } @@ -426,7 +428,7 @@ unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I, } else { // If one of the registers aliased to the current register is // compatible, use it. - for (const unsigned *AliasIt = MRI->getAliasSet(R); + for (const unsigned *AliasIt = TRI->getAliasSet(R); *AliasIt; ++AliasIt) { if (RC->contains(*AliasIt) && // If this is pinned down for some reason, don't use it. For @@ -477,8 +479,9 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, // If the virtual register is already available, just update the instruction // and return. if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) { - MarkPhysRegRecentlyUsed(PR); // Already have this value available! + MarkPhysRegRecentlyUsed(PR); // Already have this value available! MI->getOperand(OpNum).setReg(PR); // Assign the input register + getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum); return MI; } @@ -491,18 +494,7 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, if (PhysReg) { // Register is available, allocate it! assignVirtToPhysReg(VirtReg, PhysReg); } else { // No registers available. - // If we can fold this spill into this instruction, do so now. - SmallVector Ops; - Ops.push_back(OpNum); - if (MachineInstr* FMI = TII->foldMemoryOperand(MI, Ops, FrameIndex)) { - ++NumFolded; - // Update kill/dead flags. - FMI->copyKillDeadInfo(MI); - return MBB.insert(MBB.erase(MI), FMI); - } - - // It looks like we can't fold this virtual register load into this - // instruction. Force some poor hapless value out of the register file to + // Force some poor hapless value out of the register file to // make room for the new register, and reload it. PhysReg = getReg(MBB, MI, VirtReg); } @@ -510,7 +502,7 @@ MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, markVirtRegModified(VirtReg, false); // Note that this reg was just reloaded DOUT << " Reloading %reg" << VirtReg << " into " - << MRI->getName(PhysReg) << "\n"; + << TRI->getName(PhysReg) << "\n"; // Add move instruction(s) const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); @@ -557,14 +549,14 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // If this is the first basic block in the machine function, add live-in // registers as active. - if (&MBB == &*MF->begin()) { - for (MachineRegisterInfo::livein_iterator I=MF->getRegInfo().livein_begin(), - E = MF->getRegInfo().livein_end(); I != E; ++I) { - unsigned Reg = I->first; + if (&MBB == &*MF->begin() || MBB.isLandingPad()) { + for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), + E = MBB.livein_end(); I != E; ++I) { + unsigned Reg = *I; MF->getRegInfo().setPhysRegUsed(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now AddToPhysRegsUseOrder(Reg); - for (const unsigned *AliasSet = MRI->getSubRegisters(Reg); + for (const unsigned *AliasSet = TRI->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { AddToPhysRegsUseOrder(*AliasSet); @@ -581,9 +573,9 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { const TargetInstrDesc &TID = MI->getDesc(); DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI; DOUT << " Regs have values: "; - for (unsigned i = 0; i != MRI->getNumRegs(); ++i) + for (unsigned i = 0; i != TRI->getNumRegs(); ++i) if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) - DOUT << "[" << MRI->getName(i) + DOUT << "[" << TRI->getName(i) << ",%reg" << PhysRegsUsed[i] << "] "; DOUT << "\n"); @@ -619,7 +611,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { MachineOperand& MO = MI->getOperand(i); // here we are looking for only used operands (never def&use) if (MO.isRegister() && !MO.isDef() && MO.getReg() && !MO.isImplicit() && - MRegisterInfo::isVirtualRegister(MO.getReg())) + TargetRegisterInfo::isVirtualRegister(MO.getReg())) MI = reloadVirtReg(MBB, MI, i); } @@ -630,7 +622,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = Kills.size(); i != e; ++i) { unsigned VirtReg = Kills[i]; unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { + if (TargetRegisterInfo::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); @@ -645,14 +637,14 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { } if (PhysReg) { - DOUT << " Last use of " << MRI->getName(PhysReg) + DOUT << " Last use of " << TRI->getName(PhysReg) << "[%reg" << VirtReg <<"], removing it from live set\n"; removePhysReg(PhysReg); - for (const unsigned *AliasSet = MRI->getSubRegisters(PhysReg); + for (const unsigned *AliasSet = TRI->getSubRegisters(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { DOUT << " Last use of " - << MRI->getName(*AliasSet) + << TRI->getName(*AliasSet) << "[%reg" << VirtReg <<"], removing it from live set\n"; removePhysReg(*AliasSet); } @@ -665,7 +657,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); if (MO.isRegister() && MO.isDef() && !MO.isImplicit() && MO.getReg() && - MRegisterInfo::isPhysicalRegister(MO.getReg())) { + TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { unsigned Reg = MO.getReg(); if (PhysRegsUsed[Reg] == -2) continue; // Something like ESP. // These are extra physical register defs when a sub-register @@ -678,7 +670,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { PhysRegsUsed[Reg] = 0; // It is free and reserved now AddToPhysRegsUseOrder(Reg); - for (const unsigned *AliasSet = MRI->getSubRegisters(Reg); + for (const unsigned *AliasSet = TRI->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { MF->getRegInfo().setPhysRegUsed(*AliasSet); @@ -700,7 +692,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { PhysRegsUsed[Reg] = 0; // It is free and reserved now } MF->getRegInfo().setPhysRegUsed(Reg); - for (const unsigned *AliasSet = MRI->getSubRegisters(Reg); + for (const unsigned *AliasSet = TRI->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { AddToPhysRegsUseOrder(*AliasSet); @@ -726,7 +718,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); if (MO.isRegister() && MO.isDef() && MO.getReg() && - MRegisterInfo::isVirtualRegister(MO.getReg())) { + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { unsigned DestVirtReg = MO.getReg(); unsigned DestPhysReg; @@ -736,6 +728,8 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { MF->getRegInfo().setPhysRegUsed(DestPhysReg); markVirtRegModified(DestVirtReg); getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0); + DOUT << " Assigning " << TRI->getName(DestPhysReg) + << " to %reg" << DestVirtReg << "\n"; MI->getOperand(i).setReg(DestPhysReg); // Assign the output register } } @@ -746,7 +740,7 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) { unsigned VirtReg = DeadDefs[i]; unsigned PhysReg = VirtReg; - if (MRegisterInfo::isVirtualRegister(VirtReg)) { + if (TargetRegisterInfo::isVirtualRegister(VirtReg)) { unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg); PhysReg = PhysRegSlot; assert(PhysReg != 0); @@ -757,14 +751,14 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { } if (PhysReg) { - DOUT << " Register " << MRI->getName(PhysReg) + DOUT << " Register " << TRI->getName(PhysReg) << " [%reg" << VirtReg << "] is never used, removing it frame live list\n"; removePhysReg(PhysReg); - for (const unsigned *AliasSet = MRI->getAliasSet(PhysReg); + for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - DOUT << " Register " << MRI->getName(*AliasSet) + DOUT << " Register " << TRI->getName(*AliasSet) << " [%reg" << *AliasSet << "] is never used, removing it frame live list\n"; removePhysReg(*AliasSet); @@ -775,25 +769,25 @@ void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) { // Finally, if this is a noop copy instruction, zap it. unsigned SrcReg, DstReg; - if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) { + if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) MBB.erase(MI); - } } MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); // Spill all physical registers holding virtual registers now. - for (unsigned i = 0, e = MRI->getNumRegs(); i != e; ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) + if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) { if (unsigned VirtReg = PhysRegsUsed[i]) spillVirtReg(MBB, MI, VirtReg, i); else removePhysReg(i); + } #if 0 // This checking code is very expensive. bool AllOk = true; - for (unsigned i = MRegisterInfo::FirstVirtualRegister, + for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) if (unsigned PR = Virt2PhysRegMap[i]) { cerr << "Register still mapped: " << i << " -> " << PR << "\n"; @@ -815,16 +809,16 @@ bool RALocal::runOnMachineFunction(MachineFunction &Fn) { DOUT << "Machine Function " << "\n"; MF = &Fn; TM = &Fn.getTarget(); - MRI = TM->getRegisterInfo(); + TRI = TM->getRegisterInfo(); TII = TM->getInstrInfo(); - PhysRegsUsed.assign(MRI->getNumRegs(), -1); + PhysRegsUsed.assign(TRI->getNumRegs(), -1); // At various places we want to efficiently check to see whether a register // is allocatable. To handle this, we mark all unallocatable registers as // being pinned down, permanently. { - BitVector Allocable = MRI->getAllocatableSet(Fn); + BitVector Allocable = TRI->getAllocatableSet(Fn); for (unsigned i = 0, e = Allocable.size(); i != e; ++i) if (!Allocable[i]) PhysRegsUsed[i] = -2; // Mark the reg unallocable. @@ -835,7 +829,7 @@ bool RALocal::runOnMachineFunction(MachineFunction &Fn) { unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); Virt2PhysRegMap.grow(LastVirtReg); Virt2LastUseMap.grow(LastVirtReg); - VirtRegModified.resize(LastVirtReg+1-MRegisterInfo::FirstVirtualRegister); + VirtRegModified.resize(LastVirtReg+1-TargetRegisterInfo::FirstVirtualRegister); // Loop over all of the basic blocks, eliminating virtual register references for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();