X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBase.cpp;h=2e433811f44a5593b95c78f4a7e9366a6f899bfe;hb=ceaf829339bcd0719a43b3e8c22eaab7a973d37d;hp=1f824a8fdbf12f6a79c7f608f76688ec5de270cf;hpb=812cda9a5cc26b1f8dda6f909bf5062c215b65d7;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBase.cpp b/lib/CodeGen/RegAllocBase.cpp index 1f824a8fdbf..2e433811f44 100644 --- a/lib/CodeGen/RegAllocBase.cpp +++ b/lib/CodeGen/RegAllocBase.cpp @@ -14,14 +14,14 @@ #define DEBUG_TYPE "regalloc" #include "RegAllocBase.h" -#include "LiveRegMatrix.h" #include "Spiller.h" -#include "VirtRegMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveRangeEdit.h" +#include "llvm/CodeGen/LiveRegMatrix.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" #ifndef NDEBUG @@ -35,8 +35,6 @@ using namespace llvm; -STATISTIC(NumAssigned , "Number of registers assigned"); -STATISTIC(NumUnassigned , "Number of registers unassigned"); STATISTIC(NumNewQueued , "Number of new live ranges queued"); // Temporary verification option until we can put verification inside @@ -45,72 +43,26 @@ static cl::opt VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), cl::desc("Verify during register allocation")); -const char *RegAllocBase::TimerGroupName = "Register Allocation"; +const char RegAllocBase::TimerGroupName[] = "Register Allocation"; bool RegAllocBase::VerifyEnabled = false; -#ifndef NDEBUG -// Verify each LiveIntervalUnion. -void RegAllocBase::verify() { - LiveVirtRegBitSet VisitedVRegs; - OwningArrayPtr - unionVRegs(new LiveVirtRegBitSet[TRI->getNumRegs()]); - - // Verify disjoint unions. - for (unsigned PhysReg = 0, NumRegs = TRI->getNumRegs(); PhysReg != NumRegs; - ++PhysReg) { - DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI)); - LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg]; - PhysReg2LiveUnion[PhysReg].verify(VRegs); - // Union + intersection test could be done efficiently in one pass, but - // don't add a method to SparseBitVector unless we really need it. - assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions"); - VisitedVRegs |= VRegs; - } - - // Verify vreg coverage. - for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(i); - if (MRI->reg_nodbg_empty(Reg)) - continue; - if (!VRM->hasPhys(Reg)) continue; // spilled? - LiveInterval &LI = LIS->getInterval(Reg); - if (LI.empty()) continue; // unionVRegs will only be filled if li is - // non-empty - unsigned PhysReg = VRM->getPhys(Reg); - if (!unionVRegs[PhysReg].test(Reg)) { - dbgs() << "LiveVirtReg " << PrintReg(Reg, TRI) << " not in union " - << TRI->getName(PhysReg) << "\n"; - llvm_unreachable("unallocated live vreg"); - } - } - // FIXME: I'm not sure how to verify spilled intervals. -} -#endif //!NDEBUG - //===----------------------------------------------------------------------===// // RegAllocBase Implementation //===----------------------------------------------------------------------===// -void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) { - NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled); +// Pin the vtable to this file. +void RegAllocBase::anchor() {} + +void RegAllocBase::init(VirtRegMap &vrm, + LiveIntervals &lis, + LiveRegMatrix &mat) { TRI = &vrm.getTargetRegInfo(); MRI = &vrm.getRegInfo(); VRM = &vrm; LIS = &lis; + Matrix = &mat; MRI->freezeReservedRegs(vrm.getMachineFunction()); RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); - - const unsigned NumRegs = TRI->getNumRegs(); - if (NumRegs != PhysReg2LiveUnion.size()) { - PhysReg2LiveUnion.init(UnionAllocator, NumRegs); - // Cache an interferece query for each physical reg - Queries.reset(new LiveIntervalUnion::Query[NumRegs]); - } -} - -void RegAllocBase::releaseMemory() { - for (unsigned r = 0, e = PhysReg2LiveUnion.size(); r != e; ++r) - PhysReg2LiveUnion[r].clear(); } // Visit all the live registers. If they are already assigned to a physical @@ -118,14 +70,6 @@ void RegAllocBase::releaseMemory() { // them on the priority queue for later assignment. void RegAllocBase::seedLiveRegs() { NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); - // Physregs. - for (unsigned Reg = 1, e = TRI->getNumRegs(); Reg != e; ++Reg) { - if (!LIS->hasInterval(Reg)) - continue; - PhysReg2LiveUnion[Reg].unify(LIS->getInterval(Reg)); - } - - // Virtregs. for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { unsigned Reg = TargetRegisterInfo::index2VirtReg(i); if (MRI->reg_nodbg_empty(Reg)) @@ -134,35 +78,6 @@ void RegAllocBase::seedLiveRegs() { } } -void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) { - // FIXME: This diversion is temporary. - if (Matrix) { - Matrix->assign(VirtReg, PhysReg); - return; - } - DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) - << " to " << PrintReg(PhysReg, TRI) << '\n'); - assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); - VRM->assignVirt2Phys(VirtReg.reg, PhysReg); - MRI->setPhysRegUsed(PhysReg); - PhysReg2LiveUnion[PhysReg].unify(VirtReg); - ++NumAssigned; -} - -void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) { - // FIXME: This diversion is temporary. - if (Matrix) { - Matrix->unassign(VirtReg); - return; - } - DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) - << " from " << PrintReg(PhysReg, TRI) << '\n'); - assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign"); - PhysReg2LiveUnion[PhysReg].extract(VirtReg); - VRM->clearVirt(VirtReg.reg); - ++NumUnassigned; -} - // Top-level driver to manage the queue of unassigned VirtRegs and call the // selectOrSplit implementation. void RegAllocBase::allocatePhysRegs() { @@ -180,23 +95,20 @@ void RegAllocBase::allocatePhysRegs() { } // Invalidate all interference queries, live ranges could have changed. - invalidateVirtRegs(); - if (Matrix) - Matrix->invalidateVirtRegs(); + Matrix->invalidateVirtRegs(); // selectOrSplit requests the allocator to return an available physical // register if possible and populate a list of new live intervals that // result from splitting. DEBUG(dbgs() << "\nselectOrSplit " - << MRI->getRegClass(VirtReg->reg)->getName() - << ':' << PrintReg(VirtReg->reg) << ' ' << *VirtReg << '\n'); - typedef SmallVector VirtRegVec; + << MRI->getRegClass(VirtReg->reg)->getName() + << ':' << *VirtReg << " w=" << VirtReg->weight << '\n'); + typedef SmallVector VirtRegVec; VirtRegVec SplitVRegs; unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); if (AvailablePhysReg == ~0u) { // selectOrSplit failed to find a register! - const char *Msg = "ran out of registers during register allocation"; // Probably caused by an inline asm. MachineInstr *MI; for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); @@ -204,9 +116,9 @@ void RegAllocBase::allocatePhysRegs() { if (MI->isInlineAsm()) break; if (MI) - MI->emitError(Msg); + MI->emitError("inline assembly requires more registers than available"); else - report_fatal_error(Msg); + report_fatal_error("ran out of registers during register allocation"); // Keep going after reporting the error. VRM->assignVirt2Phys(VirtReg->reg, RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); @@ -214,11 +126,11 @@ void RegAllocBase::allocatePhysRegs() { } if (AvailablePhysReg) - assign(*VirtReg, AvailablePhysReg); + Matrix->assign(*VirtReg, AvailablePhysReg); for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); I != E; ++I) { - LiveInterval *SplitVirtReg = *I; + LiveInterval *SplitVirtReg = &LIS->getInterval(*I); assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); @@ -233,14 +145,3 @@ void RegAllocBase::allocatePhysRegs() { } } } - -// Check if this live virtual register interferes with a physical register. If -// not, then check for interference on each register that aliases with the -// physical register. Return the interfering register. -unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg, - unsigned PhysReg) { - for (MCRegAliasIterator AI(PhysReg, TRI, true); AI.isValid(); ++AI) - if (query(VirtReg, *AI).checkInterference()) - return *AI; - return 0; -}