X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBigBlock.cpp;h=38fb5e6894d10198020a77b25cd0a7acd343f72b;hb=08e78b18b8ef2c939ee95469662c98e23846d860;hp=c3ae77362343e33faf4409611fb789ed7468ea5a;hpb=a8c768293966822840199b496a9b020b6b460e8d;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBigBlock.cpp b/lib/CodeGen/RegAllocBigBlock.cpp index c3ae7736234..38fb5e6894d 100644 --- a/lib/CodeGen/RegAllocBigBlock.cpp +++ b/lib/CodeGen/RegAllocBigBlock.cpp @@ -2,11 +2,15 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // +// This file implements the RABigBlock class +// +//===----------------------------------------------------------------------===// + // This register allocator is derived from RegAllocLocal.cpp. Like it, this // allocator works on one basic block at a time, oblivious to others. // However, the algorithm used here is suited for long blocks of @@ -28,8 +32,8 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/SSARegMap.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/Target/TargetInstrInfo.h" @@ -53,104 +57,126 @@ namespace { bigBlockRegAlloc("bigblock", " Big-block register allocator", createBigBlockRegisterAllocator); +/// VRegKeyInfo - Defines magic values required to use VirtRegs as DenseMap +/// keys. struct VRegKeyInfo { static inline unsigned getEmptyKey() { return -1U; } static inline unsigned getTombstoneKey() { return -2U; } + static bool isEqual(unsigned LHS, unsigned RHS) { return LHS == RHS; } static unsigned getHashValue(const unsigned &Key) { return Key; } }; + +/// This register allocator is derived from RegAllocLocal.cpp. Like it, this +/// allocator works on one basic block at a time, oblivious to others. +/// However, the algorithm used here is suited for long blocks of +/// instructions - registers are spilled by greedily choosing those holding +/// values that will not be needed for the longest amount of time. This works +/// particularly well for blocks with 10 or more times as many instructions +/// as machine registers, but can be used for general code. +/// +/// TODO: - automagically invoke linearscan for (groups of) small BBs? +/// - break ties when picking regs? (probably not worth it in a +/// JIT context) +/// class VISIBILITY_HIDDEN RABigBlock : public MachineFunctionPass { public: static char ID; RABigBlock() : MachineFunctionPass((intptr_t)&ID) {} private: + /// TM - For getting at TargetMachine info + /// const TargetMachine *TM; + + /// MF - Our generic MachineFunction pointer + /// MachineFunction *MF; - const MRegisterInfo *RegInfo; - LiveVariables *LV; - - // InsnTimes - maps machine instructions to their "execute times" - std::map InsnTimes; - // VRegReadTable - maps VRegs in a BB to the set of times they are read - DenseMap*, VRegKeyInfo> VRegReadTable; + /// RegInfo - For dealing with machine register info (aliases, folds + /// etc) + const TargetRegisterInfo *RegInfo; - // StackSlotForVirtReg - Maps virtual regs to the frame index where these - // values are spilled. - std::map StackSlotForVirtReg; + typedef SmallVector VRegTimes; - // Virt2PhysRegMap - This map contains entries for each virtual register - // that is currently available in a physical register. + /// VRegReadTable - maps VRegs in a BB to the set of times they are read + /// + DenseMap VRegReadTable; + + /// VRegReadIdx - keeps track of the "current time" in terms of + /// positions in VRegReadTable + DenseMap VRegReadIdx; + + /// StackSlotForVirtReg - Maps virtual regs to the frame index where these + /// values are spilled. + IndexedMap StackSlotForVirtReg; + + /// Virt2PhysRegMap - This map contains entries for each virtual register + /// that is currently available in a physical register. IndexedMap Virt2PhysRegMap; + /// 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, and to -2 if it is not + /// allocatable. If the entry for a physical register is -1, then the + /// physical register is "not in the map". + /// + std::vector PhysRegsUsed; + + /// VirtRegModified - This bitset contains information about which virtual + /// registers need to be spilled back to memory when their registers are + /// scavenged. If a virtual register has simply been rematerialized, there + /// is no reason to spill it to memory when we need the register back. + /// + std::vector VirtRegModified; + + /// MBBLastInsnTime - the number of the the last instruction in MBB + /// + int MBBLastInsnTime; + + /// MBBCurTime - the number of the the instruction being currently processed + /// + int MBBCurTime; + unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { return Virt2PhysRegMap[VirtReg]; } - // 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, and to -2 if it is not - // allocatable. If the entry for a physical register is -1, then the - // physical register is "not in the map". - // - std::vector PhysRegsUsed; - - // PhysRegsUseOrder - This contains a list of the physical registers that - // currently have a virtual register value in them. This list provides an - // ordering of registers, imposing a reallocation order. This list is only - // used if all registers are allocated and we have to spill one, in which - // case we spill the least recently used register. Entries at the front of - // the list are the least recently used registers, entries at the back are - // the most recently used. - // - std::vector PhysRegsUseOrder; - - // VirtRegModified - This bitset contains information about which virtual - // registers need to be spilled back to memory when their registers are - // scavenged. If a virtual register has simply been rematerialized, there - // is no reason to spill it to memory when we need the register back. - // - std::vector VirtRegModified; + unsigned &getVirt2StackSlot(unsigned VirtReg) { + return StackSlotForVirtReg[VirtReg]; + } + /// markVirtRegModified - Lets us flip bits in the VirtRegModified bitset + /// void markVirtRegModified(unsigned Reg, bool Val = true) { - assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); - Reg -= MRegisterInfo::FirstVirtualRegister; - if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1); + assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!"); + Reg -= TargetRegisterInfo::FirstVirtualRegister; + if (VirtRegModified.size() <= Reg) + VirtRegModified.resize(Reg+1); VirtRegModified[Reg] = Val; } + /// isVirtRegModified - Lets us query the VirtRegModified bitset + /// 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]; - } - - void MarkPhysRegRecentlyUsed(unsigned Reg) { - if (PhysRegsUseOrder.empty() || - PhysRegsUseOrder.back() == Reg) return; // Already most recently used - - for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i) - if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) { - unsigned RegMatch = PhysRegsUseOrder[i-1]; // remove from middle - PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1); - // Add it to the end of the list - PhysRegsUseOrder.push_back(RegMatch); - if (RegMatch == Reg) - return; // Found an exact match, exit early - } + return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister]; } public: + /// getPassName - returns the BigBlock allocator's name + /// virtual const char *getPassName() const { return "BigBlock Register Allocator"; } + /// getAnalaysisUsage - declares the required analyses + /// virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); AU.addRequiredID(PHIEliminationID); AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); @@ -158,12 +184,15 @@ namespace { private: /// runOnMachineFunction - Register allocate the whole function + /// bool runOnMachineFunction(MachineFunction &Fn); /// AllocateBasicBlock - Register allocate the specified basic block. + /// void AllocateBasicBlock(MachineBasicBlock &MBB); /// FillVRegReadTable - Fill out the table of vreg read times given a BB + /// void FillVRegReadTable(MachineBasicBlock &MBB); /// areRegsEqual - This method returns true if the specified registers are @@ -209,13 +238,6 @@ namespace { /// void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); - /// liberatePhysReg - Make sure the specified physical register is available - /// for use. If there is currently a value in it, it is either moved out of - /// the way or spilled to memory. - /// - void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I, - unsigned PhysReg); - /// isPhysRegAvailable - Return true if the specified physical register is /// free and available for use. This also includes checking to see if /// aliased registers are all free... @@ -256,17 +278,17 @@ namespace { /// to be held on the stack. int RABigBlock::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { // Find the location Reg would belong... - std::map::iterator I =StackSlotForVirtReg.lower_bound(VirtReg); + int FrameIdx = getVirt2StackSlot(VirtReg); - if (I != StackSlotForVirtReg.end() && I->first == VirtReg) - return I->second; // Already has space allocated? + if (FrameIdx) + return FrameIdx - 1; // Already has space allocated? // Allocate a new stack object for this spill location... - int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), + FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(), RC->getAlignment()); // Assign the slot... - StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx)); + getVirt2StackSlot(VirtReg) = FrameIdx + 1; return FrameIdx; } @@ -276,11 +298,6 @@ int RABigBlock::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC /// void RABigBlock::removePhysReg(unsigned PhysReg) { PhysRegsUsed[PhysReg] = -1; // PhyReg no longer used - - std::vector::iterator It = - std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg); - if (It != PhysRegsUseOrder.end()) - PhysRegsUseOrder.erase(It); } @@ -296,6 +313,9 @@ void RABigBlock::spillVirtReg(MachineBasicBlock &MBB, " the intended one."); DOUT << " Spilling register " << RegInfo->getName(PhysReg) << " containing %reg" << VirtReg; + + const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); + if (!isVirtRegModified(VirtReg)) DOUT << " which has not been modified, so no store necessary!"; @@ -303,10 +323,10 @@ void RABigBlock::spillVirtReg(MachineBasicBlock &MBB, // register. We only need to spill it into its stack slot if it has been // modified. if (isVirtRegModified(VirtReg)) { - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); DOUT << " to stack slot #" << FrameIndex; - RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); + TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIndex, RC); ++NumStores; // Update statistics } @@ -335,18 +355,7 @@ void RABigBlock::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, *AliasSet; ++AliasSet) if (PhysRegsUsed[*AliasSet] != -1 && // Spill aliased register. PhysRegsUsed[*AliasSet] != -2) // If allocatable. - if (PhysRegsUsed[*AliasSet] == 0) { - // This must have been a dead def due to something like this: - // %EAX := - // := op %AL - // No more use of %EAX, %AH, etc. - // %EAX isn't dead upon definition, but %AH is. However %AH isn't - // an operand of definition MI so it's not marked as such. - DOUT << " Register " << RegInfo->getName(*AliasSet) - << " [%reg" << *AliasSet - << "] is never used, removing it frame live list\n"; - removePhysReg(*AliasSet); - } else + if (PhysRegsUsed[*AliasSet]) spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet); } } @@ -362,7 +371,6 @@ void RABigBlock::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { // it holds VirtReg. PhysRegsUsed[PhysReg] = VirtReg; getVirt2PhysRegMapSlot(VirtReg) = PhysReg; - PhysRegsUseOrder.push_back(PhysReg); // New use of PhysReg } @@ -382,8 +390,7 @@ bool RABigBlock::isPhysRegAvailable(unsigned PhysReg) const { return true; } - -//////// FIX THIS: + /// getFreeReg - Look to see if there is a free register available in the /// specified register class. If not, return 0. /// @@ -402,23 +409,13 @@ unsigned RABigBlock::getFreeReg(const TargetRegisterClass *RC) { } -/// liberatePhysReg - Make sure the specified physical register is available for -/// use. If there is currently a value in it, it is either moved out of the way -/// or spilled to memory. -/// -void RABigBlock::liberatePhysReg(MachineBasicBlock &MBB, - MachineBasicBlock::iterator &I, - unsigned PhysReg) { - spillPhysReg(MBB, I, PhysReg); -} - /// chooseReg - Pick a physical register to hold the specified /// virtual register by choosing the one whose value will be read /// furthest in the future. /// unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, unsigned VirtReg) { - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); // First check to see if we have a free register of the requested type... unsigned PhysReg = getFreeReg(RC); @@ -426,9 +423,9 @@ unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, // read at the most distant point in time. if (PhysReg == 0) { unsigned delay=0, longest_delay=0; - SmallVector *ReadTimes; + VRegTimes* ReadTimes; - unsigned curTime = InsnTimes[I]; + unsigned curTime = MBBCurTime; // for all physical regs in the RC, for(TargetRegisterClass::iterator pReg = RC->begin(); @@ -436,11 +433,23 @@ unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, // how long until they're read? if(PhysRegsUsed[*pReg]>0) { // ignore non-allocatable regs ReadTimes = VRegReadTable[PhysRegsUsed[*pReg]]; - SmallVector::iterator pt = - std::lower_bound(ReadTimes->begin(), - ReadTimes->end(), - curTime); - delay = *pt - curTime; + if(ReadTimes && !ReadTimes->empty()) { + unsigned& pt = VRegReadIdx[PhysRegsUsed[*pReg]]; + while(pt < ReadTimes->size() && (*ReadTimes)[pt] < curTime) { + ++pt; + } + + if(pt < ReadTimes->size()) + delay = (*ReadTimes)[pt] - curTime; + else + delay = MBBLastInsnTime + 1 - curTime; + } else { + // This register is only defined, but never + // read in this MBB. Therefore the next read + // happens after the end of this MBB + delay = MBBLastInsnTime + 1 - curTime; + } + if(delay > longest_delay) { longest_delay = delay; @@ -448,9 +457,23 @@ unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, } } } + + if(PhysReg == 0) { // ok, now we're desperate. We couldn't choose + // a register to spill by looking through the + // read timetable, so now we just spill the + // first allocatable register we find. + + // for all physical regs in the RC, + for(TargetRegisterClass::iterator pReg = RC->begin(); + pReg != RC->end(); ++pReg) { + // if we find a register we can spill + if(PhysRegsUsed[*pReg]>=-1) + PhysReg = *pReg; // choose it to be spilled + } + } - assert(PhysReg && "couldn't grab a register from the table?"); - // TODO: assert that RC->contains(PhysReg) / handle aliased registers + assert(PhysReg && "couldn't choose a register to spill :( "); + // TODO: assert that RC->contains(PhysReg) / handle aliased registers? // since we needed to look in the table we need to spill this register. spillPhysReg(MBB, I, PhysReg); @@ -476,6 +499,7 @@ unsigned RABigBlock::chooseReg(MachineBasicBlock &MBB, MachineInstr *I, MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, unsigned OpNum) { unsigned VirtReg = MI->getOperand(OpNum).getReg(); + const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo(); // If the virtual register is already available in a physical register, // just update the instruction and return. @@ -486,7 +510,7 @@ MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI // Otherwise, if we have free physical registers available to hold the // value, use them. - const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); + const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); unsigned PhysReg = getFreeReg(RC); int FrameIndex = getStackSpaceFor(VirtReg, RC); @@ -494,11 +518,11 @@ MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI assignVirtToPhysReg(VirtReg, PhysReg); } else { // no free registers available. // try to fold the spill into the instruction - if(MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)) { + SmallVector Ops; + Ops.push_back(OpNum); + if(MachineInstr* FMI = TII->foldMemoryOperand(*MF, MI, Ops, 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); + FMI->copyKillDeadInfo(MI); return MBB.insert(MBB.erase(MI), FMI); } @@ -514,10 +538,10 @@ MachineInstr *RABigBlock::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI << RegInfo->getName(PhysReg) << "\n"; // Add move instruction(s) - RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); + TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC); ++NumLoads; // Update statistics - MF->setPhysRegUsed(PhysReg); + MF->getRegInfo().setPhysRegUsed(PhysReg); MI->getOperand(OpNum).setReg(PhysReg); // Assign the input register return MI; } @@ -533,25 +557,58 @@ void RABigBlock::FillVRegReadTable(MachineBasicBlock &MBB) { for(ReadTime=0, MII = MBB.begin(); MII != MBB.end(); ++ReadTime, ++MII) { MachineInstr *MI = MII; - InsnTimes[MI] = ReadTime; - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& MO = MI->getOperand(i); // look for vreg reads.. if (MO.isRegister() && !MO.isDef() && MO.getReg() && - MRegisterInfo::isVirtualRegister(MO.getReg())) { - // ..and add them to the read table. - if(!VRegReadTable[MO.getReg()]) - VRegReadTable[MO.getReg()] = new SmallVector; - - VRegReadTable[MO.getReg()]->push_back(ReadTime); + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { + // ..and add them to the read table. + VRegTimes* &Times = VRegReadTable[MO.getReg()]; + if(!VRegReadTable[MO.getReg()]) { + Times = new VRegTimes; + VRegReadIdx[MO.getReg()] = 0; + } + Times->push_back(ReadTime); } } } + MBBLastInsnTime = ReadTime; + + for(DenseMap::iterator Reads = VRegReadTable.begin(); + Reads != VRegReadTable.end(); ++Reads) { + if(Reads->second) { + DOUT << "Reads[" << Reads->first << "]=" << Reads->second->size() << "\n"; + } + } +} + +/// isReadModWriteImplicitKill - True if this is an implicit kill for a +/// read/mod/write register, i.e. update partial register. +static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) { + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() && + MO.isDef() && !MO.isDead()) + return true; + } + return false; } +/// isReadModWriteImplicitDef - True if this is an implicit def for a +/// read/mod/write register, i.e. update partial register. +static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) { + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand& MO = MI->getOperand(i); + if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() && + !MO.isDef() && MO.isKill()) + return true; + } + return false; +} + + void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // loop over each instruction MachineBasicBlock::iterator MII = MBB.begin(); @@ -563,28 +620,29 @@ void RABigBlock::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 (MachineFunction::livein_iterator I = MF->livein_begin(), - E = MF->livein_end(); I != E; ++I) { + for (MachineRegisterInfo::livein_iterator + I = MF->getRegInfo().livein_begin(), + E = MF->getRegInfo().livein_end(); I != E; ++I) { unsigned Reg = I->first; - MF->setPhysRegUsed(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now - PhysRegsUseOrder.push_back(Reg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUseOrder.push_back(*AliasSet); PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } } // Otherwise, sequentially allocate each instruction in the MBB. + MBBCurTime = -1; while (MII != MBB.end()) { MachineInstr *MI = MII++; - const TargetInstrDescriptor &TID = TII.get(MI->getOpcode()); - DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI; + MBBCurTime++; + const TargetInstrDesc &TID = MI->getDesc(); + DEBUG(DOUT << "\nTime=" << MBBCurTime << " Starting RegAlloc of: " << *MI; DOUT << " Regs have values: "; for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i) if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) @@ -592,19 +650,18 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { << ",%reg" << PhysRegsUsed[i] << "] "; DOUT << "\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. - if (TID.ImplicitUses) { - for (const unsigned *ImplicitUses = TID.ImplicitUses; - *ImplicitUses; ++ImplicitUses) - MarkPhysRegRecentlyUsed(*ImplicitUses); - } - SmallVector Kills; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand& MO = MI->getOperand(i); - if (MO.isRegister() && MO.isKill()) - Kills.push_back(MO.getReg()); + if (MO.isRegister() && MO.isKill()) { + if (!MO.isImplicit()) + Kills.push_back(MO.getReg()); + else if (!isReadModWriteImplicitKill(MI, MO.getReg())) + // These are extra physical register kills when a sub-register + // is defined (def of a sub-register is a read/mod/write of the + // larger registers). Ignore. + Kills.push_back(MO.getReg()); + } } // Get the used operands into registers. This has the potential to spill @@ -617,7 +674,7 @@ void RABigBlock::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); } @@ -628,7 +685,7 @@ void RABigBlock::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); @@ -637,13 +694,16 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { } else if (PhysRegsUsed[PhysReg] == -2) { // Unallocatable register dead, ignore. continue; + } else { + assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) && + "Silently clearing a virtual register?"); } if (PhysReg) { DOUT << " Last use of " << RegInfo->getName(PhysReg) << "[%reg" << VirtReg <<"], removing it from live set\n"; removePhysReg(PhysReg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(PhysReg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { DOUT << " Last use of " @@ -660,46 +720,42 @@ void RABigBlock::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. - - MF->setPhysRegUsed(Reg); + // These are extra physical register defs when a sub-register + // is defined (def of a sub-register is a read/mod/write of the + // larger registers). Ignore. + if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; + + MF->getRegInfo().setPhysRegUsed(Reg); spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg PhysRegsUsed[Reg] = 0; // It is free and reserved now - PhysRegsUseOrder.push_back(Reg); - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - PhysRegsUseOrder.push_back(*AliasSet); PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - MF->setPhysRegUsed(*AliasSet); + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } } // Loop over the implicit defs, spilling them as well. - if (TID.ImplicitDefs) { - for (const unsigned *ImplicitDefs = TID.ImplicitDefs; + if (TID.getImplicitDefs()) { + for (const unsigned *ImplicitDefs = TID.getImplicitDefs(); *ImplicitDefs; ++ImplicitDefs) { unsigned Reg = *ImplicitDefs; - bool IsNonAllocatable = PhysRegsUsed[Reg] == -2; - if (!IsNonAllocatable) { + if (PhysRegsUsed[Reg] != -2) { spillPhysReg(MBB, MI, Reg, true); - PhysRegsUseOrder.push_back(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now } - MF->setPhysRegUsed(Reg); - - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + MF->getRegInfo().setPhysRegUsed(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - if (!IsNonAllocatable) { - PhysRegsUseOrder.push_back(*AliasSet); - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - } - MF->setPhysRegUsed(*AliasSet); + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now + MF->getRegInfo().setPhysRegUsed(*AliasSet); } } } @@ -720,14 +776,14 @@ void RABigBlock::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; // If DestVirtReg already has a value, use it. if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) DestPhysReg = chooseReg(MBB, MI, DestVirtReg); - MF->setPhysRegUsed(DestPhysReg); + MF->getRegInfo().setPhysRegUsed(DestPhysReg); markVirtRegModified(DestVirtReg); MI->getOperand(i).setReg(DestPhysReg); // Assign the output register } @@ -739,7 +795,7 @@ void RABigBlock::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); @@ -768,39 +824,20 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { // Finally, if this is a noop copy instruction, zap it. unsigned SrcReg, DstReg; - if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg) { - LV->removeVirtualRegistersKilled(MI); - LV->removeVirtualRegistersDead(MI); + 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 = RegInfo->getNumRegs(); i != e; ++i) - if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) + 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, - e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i) - if (unsigned PR = Virt2PhysRegMap[i]) { - 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 - // pointer. - PhysRegsUseOrder.clear(); } /// runOnMachineFunction - Register allocate the whole function @@ -810,7 +847,6 @@ bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) { MF = &Fn; TM = &Fn.getTarget(); RegInfo = TM->getRegisterInfo(); - LV = &getAnalysis(); PhysRegsUsed.assign(RegInfo->getNumRegs(), -1); @@ -826,7 +862,10 @@ bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) { // initialize the virtual->physical register map to have a 'null' // mapping for all virtual registers - Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg()); + Virt2PhysRegMap.grow(MF->getRegInfo().getLastVirtReg()); + StackSlotForVirtReg.grow(MF->getRegInfo().getLastVirtReg()); + VirtRegModified.resize(MF->getRegInfo().getLastVirtReg() - + TargetRegisterInfo::FirstVirtualRegister + 1, 0); // Loop over all of the basic blocks, eliminating virtual register references for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();