X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBigBlock.cpp;h=83c9ceb37b0770ff9c3757770bc80bd2e1077e53;hb=ee888132754c709de8d2e2c5ef85531a15ed44f2;hp=9bd5d4adc1768c4b670734ebefc0b13578491f91;hpb=2e0930cf37a528a8c1d3911940287084dfccbc70;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBigBlock.cpp b/lib/CodeGen/RegAllocBigBlock.cpp index 9bd5d4adc17..83c9ceb37b0 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 was developed by Duraid Madina and 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 @@ -54,79 +58,113 @@ 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; + + /// RegInfo - For dealing with machine register info (aliases, folds + /// etc) const MRegisterInfo *RegInfo; + + /// LV - Our generic LiveVariables pointer + /// LiveVariables *LV; - // VRegReadTable - maps VRegs in a BB to the set of times they are read - // This is a sorted list typedef SmallVector VRegTimes; + /// 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. - //DenseMap StackSlotForVirtReg; + /// 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. + /// Virt2PhysRegMap - This map contains entries for each virtual register + /// that is currently available in a physical register. IndexedMap Virt2PhysRegMap; - unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { - return Virt2PhysRegMap[VirtReg]; - } - - unsigned &getVirt2StackSlot(unsigned VirtReg) { - return StackSlotForVirtReg[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". - // + /// 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. - // + /// 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 + /// MBBLastInsnTime - the number of the the last instruction in MBB + /// int MBBLastInsnTime; - // MBBCurTime - the number of the the instruction being currently processed + /// MBBCurTime - the number of the the instruction being currently processed + /// int MBBCurTime; + unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) { + return Virt2PhysRegMap[VirtReg]; + } + + 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); + 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() @@ -135,10 +173,14 @@ namespace { } 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); @@ -148,12 +190,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 @@ -199,13 +244,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... @@ -291,7 +329,7 @@ void RABigBlock::spillVirtReg(MachineBasicBlock &MBB, const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg); int FrameIndex = getStackSpaceFor(VirtReg, RC); DOUT << " to stack slot #" << FrameIndex; - RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC); + RegInfo->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIndex, RC); ++NumStores; // Update statistics } @@ -320,18 +358,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); } } @@ -366,8 +393,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. /// @@ -386,16 +412,6 @@ 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. @@ -444,9 +460,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); @@ -490,7 +520,9 @@ 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 = RegInfo->foldMemoryOperand(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. @@ -556,6 +588,30 @@ void RABigBlock::FillVRegReadTable(MachineBasicBlock &MBB) { } } +/// 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 @@ -573,7 +629,7 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { unsigned Reg = I->first; MF->setPhysRegUsed(Reg); PhysRegsUsed[Reg] = 0; // It is free and reserved now - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now @@ -600,8 +656,15 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { 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 @@ -634,13 +697,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,11 +726,15 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { MRegisterInfo::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 + // is defined (def of a sub-register is a read/mod/write of the + // larger registers). Ignore. + if (isReadModWriteImplicitDef(MI, MO.getReg())) continue; + MF->setPhysRegUsed(Reg); spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg PhysRegsUsed[Reg] = 0; // It is free and reserved now - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now @@ -679,19 +749,15 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { for (const unsigned *ImplicitDefs = TID.ImplicitDefs; *ImplicitDefs; ++ImplicitDefs) { unsigned Reg = *ImplicitDefs; - bool IsNonAllocatable = PhysRegsUsed[Reg] == -2; - if (!IsNonAllocatable) { + if (PhysRegsUsed[Reg] != -2) { spillPhysReg(MBB, MI, Reg, true); PhysRegsUsed[Reg] = 0; // It is free and reserved now } MF->setPhysRegUsed(Reg); - - for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); + for (const unsigned *AliasSet = RegInfo->getSubRegisters(Reg); *AliasSet; ++AliasSet) { if (PhysRegsUsed[*AliasSet] != -2) { - if (!IsNonAllocatable) { - PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now - } + PhysRegsUsed[*AliasSet] = 0; // It is free and reserved now MF->setPhysRegUsed(*AliasSet); } } @@ -777,22 +843,6 @@ void RABigBlock::AllocateBasicBlock(MachineBasicBlock &MBB) { 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. } /// runOnMachineFunction - Register allocate the whole function @@ -843,3 +893,4 @@ bool RABigBlock::runOnMachineFunction(MachineFunction &Fn) { FunctionPass *llvm::createBigBlockRegisterAllocator() { return new RABigBlock(); } +