X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FVirtRegMap.cpp;h=ba1f571f25a9677721fe6c63d79802d29805d68d;hb=a3e49ea99afc3c9f43953bdc3b3bd77970ed510d;hp=f892e94e54d133a16ea585e2ac98cd0345807995;hpb=92fca73d521758012e0e425eac33bb77e888112e;p=oota-llvm.git diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index f892e94e54d..ba1f571f25a 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -16,7 +16,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/VirtRegMap.h" #include "LiveDebugVariables.h" #include "llvm/ADT/STLExtras.h" @@ -37,9 +36,12 @@ #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + STATISTIC(NumSpillSlots, "Number of spill slots allocated"); STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); @@ -53,8 +55,8 @@ INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { MRI = &mf.getRegInfo(); - TII = mf.getTarget().getInstrInfo(); - TRI = mf.getTarget().getRegisterInfo(); + TII = mf.getSubtarget().getInstrInfo(); + TRI = mf.getSubtarget().getRegisterInfo(); MF = &mf; Virt2PhysMap.clear(); @@ -122,7 +124,7 @@ void VirtRegMap::print(raw_ostream &OS, const Module*) const { if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { OS << '[' << PrintReg(Reg, TRI) << " -> " << PrintReg(Virt2PhysMap[Reg], TRI) << "] " - << MRI->getRegClass(Reg)->getName() << "\n"; + << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n"; } } @@ -130,7 +132,7 @@ void VirtRegMap::print(raw_ostream &OS, const Module*) const { unsigned Reg = TargetRegisterInfo::index2VirtReg(i); if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] - << "] " << MRI->getRegClass(Reg)->getName() << "\n"; + << "] " << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n"; } } OS << '\n'; @@ -161,10 +163,12 @@ class VirtRegRewriter : public MachineFunctionPass { SlotIndexes *Indexes; LiveIntervals *LIS; VirtRegMap *VRM; - SparseSet PhysRegs; void rewrite(); void addMBBLiveIns(); + bool readsUndefSubreg(const MachineOperand &MO) const; + void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const; + public: static char ID; VirtRegRewriter() : MachineFunctionPass(ID) {} @@ -204,8 +208,8 @@ void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { MF = &fn; TM = &MF->getTarget(); - TRI = TM->getRegisterInfo(); - TII = TM->getInstrInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); + TII = MF->getSubtarget().getInstrInfo(); MRI = &MF->getRegInfo(); Indexes = &getAnalysis(); LIS = &getAnalysis(); @@ -234,10 +238,52 @@ bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { return true; } +void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI, + unsigned PhysReg) const { + assert(!LI.empty()); + assert(LI.hasSubRanges()); + + typedef std::pair SubRangeIteratorPair; + SmallVector SubRanges; + SlotIndex First; + SlotIndex Last; + for (const LiveInterval::SubRange &SR : LI.subranges()) { + SubRanges.push_back(std::make_pair(&SR, SR.begin())); + if (!First.isValid() || SR.segments.front().start < First) + First = SR.segments.front().start; + if (!Last.isValid() || SR.segments.back().end > Last) + Last = SR.segments.back().end; + } + + // Check all mbb start positions between First and Last while + // simulatenously advancing an iterator for each subrange. + for (SlotIndexes::MBBIndexIterator MBBI = Indexes->findMBBIndex(First); + MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) { + SlotIndex MBBBegin = MBBI->first; + // Advance all subrange iterators so that their end position is just + // behind MBBBegin (or the iterator is at the end). + unsigned LaneMask = 0; + for (auto &RangeIterPair : SubRanges) { + const LiveInterval::SubRange *SR = RangeIterPair.first; + LiveInterval::const_iterator &SRI = RangeIterPair.second; + while (SRI != SR->end() && SRI->end <= MBBBegin) + ++SRI; + if (SRI == SR->end()) + continue; + if (SRI->start <= MBBBegin) + LaneMask |= SR->LaneMask; + } + if (LaneMask == 0) + continue; + MachineBasicBlock *MBB = MBBI->second; + MBB->addLiveIn(PhysReg, LaneMask); + } +} + // Compute MBB live-in lists from virtual register live ranges and their // assignments. void VirtRegRewriter::addMBBLiveIns() { - SmallVector LiveIn; for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); if (MRI->reg_nodbg_empty(VirtReg)) @@ -250,71 +296,68 @@ void VirtRegRewriter::addMBBLiveIns() { unsigned PhysReg = VRM->getPhys(VirtReg); assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); - // Scan the segments of LI. - for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; - ++I) { - if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) - continue; - for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) - if (!LiveIn[i]->isLiveIn(PhysReg)) - LiveIn[i]->addLiveIn(PhysReg); - LiveIn.clear(); + if (LI.hasSubRanges()) { + addLiveInsForSubRanges(LI, PhysReg); + } else { + // Go over MBB begin positions and see if we have segments covering them. + // The following works because segments and the MBBIndex list are both + // sorted by slot indexes. + SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(); + for (const auto &Seg : LI) { + I = Indexes->advanceMBBIndex(I, Seg.start); + for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) { + MachineBasicBlock *MBB = I->second; + MBB->addLiveIn(PhysReg); + } + } } } + + // Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in + // each MBB's LiveIns set before calling addLiveIn on them. + for (MachineBasicBlock &MBB : *MF) + MBB.sortUniqueLiveIns(); +} + +/// Returns true if the given machine operand \p MO only reads undefined lanes. +/// The function only works for use operands with a subregister set. +bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const { + // Shortcut if the operand is already marked undef. + if (MO.isUndef()) + return true; + + unsigned Reg = MO.getReg(); + const LiveInterval &LI = LIS->getInterval(Reg); + const MachineInstr &MI = *MO.getParent(); + SlotIndex BaseIndex = LIS->getInstructionIndex(&MI); + // This code is only meant to handle reading undefined subregisters which + // we couldn't properly detect before. + assert(LI.liveAt(BaseIndex) && + "Reads of completely dead register should be marked undef already"); + unsigned SubRegIdx = MO.getSubReg(); + unsigned UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx); + // See if any of the relevant subregister liveranges is defined at this point. + for (const LiveInterval::SubRange &SR : LI.subranges()) { + if ((SR.LaneMask & UseMask) != 0 && SR.liveAt(BaseIndex)) + return false; + } + return true; } void VirtRegRewriter::rewrite() { + bool NoSubRegLiveness = !MRI->subRegLivenessEnabled(); SmallVector SuperDeads; SmallVector SuperDefs; SmallVector SuperKills; - SmallPtrSet NoReturnInsts; - - // Here we have a SparseSet to hold which PhysRegs are actually encountered - // in the MF we are about to iterate over so that later when we call - // setPhysRegUsed, we are only doing it for physRegs that were actually found - // in the program and not for all of the possible physRegs for the given - // target architecture. If the target has a lot of physRegs, then for a small - // program there will be a significant compile time reduction here. - PhysRegs.clear(); - PhysRegs.setUniverse(TRI->getNumRegs()); - - // The function with uwtable should guarantee that the stack unwinder - // can unwind the stack to the previous frame. Thus, we can't apply the - // noreturn optimization if the caller function has uwtable attribute. - bool HasUWTable = MF->getFunction()->hasFnAttribute(Attribute::UWTable); for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); MBBI != MBBE; ++MBBI) { DEBUG(MBBI->print(dbgs(), Indexes)); - bool IsExitBB = MBBI->succ_empty(); for (MachineBasicBlock::instr_iterator MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { MachineInstr *MI = MII; ++MII; - // Check if this instruction is a call to a noreturn function. If this - // is a call to noreturn function and we don't need the stack unwinding - // functionality (i.e. this function does not have uwtable attribute and - // the callee function has the nounwind attribute), then we can ignore - // the definitions set by this instruction. - if (!HasUWTable && IsExitBB && MI->isCall()) { - for (MachineInstr::mop_iterator MOI = MI->operands_begin(), - MOE = MI->operands_end(); MOI != MOE; ++MOI) { - MachineOperand &MO = *MOI; - if (!MO.isGlobal()) - continue; - const Function *Func = dyn_cast(MO.getGlobal()); - if (!Func || !Func->hasFnAttribute(Attribute::NoReturn) || - // We need to keep correct unwind information - // even if the function will not return, since the - // runtime may need it. - !Func->hasFnAttribute(Attribute::NoUnwind)) - continue; - NoReturnInsts.insert(MI); - break; - } - } - for (MachineInstr::mop_iterator MOI = MI->operands_begin(), MOE = MI->operands_end(); MOI != MOE; ++MOI) { MachineOperand &MO = *MOI; @@ -323,15 +366,6 @@ void VirtRegRewriter::rewrite() { if (MO.isRegMask()) MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); - // If we encounter a VirtReg or PhysReg then get at the PhysReg and add - // it to the physreg bitset. Later we use only the PhysRegs that were - // actually encountered in the MF to populate the MRI's used physregs. - if (MO.isReg() && MO.getReg()) - PhysRegs.insert( - TargetRegisterInfo::isVirtualRegister(MO.getReg()) ? - VRM->getPhys(MO.getReg()) : - MO.getReg()); - if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) continue; unsigned VirtReg = MO.getReg(); @@ -341,29 +375,51 @@ void VirtRegRewriter::rewrite() { assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); // Preserve semantics of sub-register operands. - if (MO.getSubReg()) { - // A virtual register kill refers to the whole register, so we may - // have to add operands for the super-register. A - // partial redef always kills and redefines the super-register. - if (MO.readsReg() && (MO.isDef() || MO.isKill())) - SuperKills.push_back(PhysReg); - - if (MO.isDef()) { - // The flag only makes sense for sub-register defs, and - // we are substituting a full physreg. An operand - // from the SuperKills list will represent the partial read of the - // super-register. - MO.setIsUndef(false); - - // Also add implicit defs for the super-register. - if (MO.isDead()) - SuperDeads.push_back(PhysReg); - else - SuperDefs.push_back(PhysReg); + unsigned SubReg = MO.getSubReg(); + if (SubReg != 0) { + if (NoSubRegLiveness) { + // A virtual register kill refers to the whole register, so we may + // have to add operands for the super-register. A + // partial redef always kills and redefines the super-register. + if (MO.readsReg() && (MO.isDef() || MO.isKill())) + SuperKills.push_back(PhysReg); + + if (MO.isDef()) { + // Also add implicit defs for the super-register. + if (MO.isDead()) + SuperDeads.push_back(PhysReg); + else + SuperDefs.push_back(PhysReg); + } + } else { + if (MO.isUse()) { + if (readsUndefSubreg(MO)) + // We need to add an flag if the subregister is + // completely undefined (and we are not adding super-register + // defs). + MO.setIsUndef(true); + } else if (!MO.isDead()) { + assert(MO.isDef()); + // Things get tricky when we ran out of lane mask bits and + // merged multiple lanes into the overflow bit: In this case + // our subregister liveness tracking isn't precise and we can't + // know what subregister parts are undefined, fall back to the + // implicit super-register def then. + unsigned LaneMask = TRI->getSubRegIndexLaneMask(SubReg); + if (TargetRegisterInfo::isImpreciseLaneMask(LaneMask)) + SuperDefs.push_back(PhysReg); + } } + // The flag only makes sense for sub-register defs, and + // we are substituting a full physreg. An operand + // from the SuperKills list will represent the partial read of the + // super-register. + if (MO.isDef()) + MO.setIsUndef(false); + // PhysReg operands cannot have subregister indexes. - PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); + PhysReg = TRI->getSubReg(PhysReg, SubReg); assert(PhysReg && "Invalid SubReg for physical register"); MO.setSubReg(0); } @@ -388,41 +444,11 @@ void VirtRegRewriter::rewrite() { // Finally, remove any identity copies. if (MI->isIdentityCopy()) { ++NumIdCopies; - if (MI->getNumOperands() == 2) { - DEBUG(dbgs() << "Deleting identity copy.\n"); - if (Indexes) - Indexes->removeMachineInstrFromMaps(MI); - // It's safe to erase MI because MII has already been incremented. - MI->eraseFromParent(); - } else { - // Transform identity copy to a KILL to deal with subregisters. - MI->setDesc(TII->get(TargetOpcode::KILL)); - DEBUG(dbgs() << "Identity copy: " << *MI); - } - } - } - } - - // Tell MRI about physical registers in use. - if (NoReturnInsts.empty()) { - for (SparseSet::iterator - RegI = PhysRegs.begin(), E = PhysRegs.end(); RegI != E; ++RegI) - if (!MRI->reg_nodbg_empty(*RegI)) - MRI->setPhysRegUsed(*RegI); - } else { - for (SparseSet::iterator - I = PhysRegs.begin(), E = PhysRegs.end(); I != E; ++I) { - unsigned Reg = *I; - if (MRI->reg_nodbg_empty(Reg)) - continue; - // Check if this register has a use that will impact the rest of the - // code. Uses in debug and noreturn instructions do not impact the - // generated code. - for (MachineInstr &It : MRI->reg_nodbg_instructions(Reg)) { - if (!NoReturnInsts.count(&It)) { - MRI->setPhysRegUsed(Reg); - break; - } + DEBUG(dbgs() << "Deleting identity copy.\n"); + if (Indexes) + Indexes->removeMachineInstrFromMaps(MI); + // It's safe to erase MI because MII has already been incremented. + MI->eraseFromParent(); } } }