diff options
Diffstat (limited to 'lib/CodeGen/VirtRegMap.cpp')
| -rw-r--r-- | lib/CodeGen/VirtRegMap.cpp | 465 |
1 files changed, 301 insertions, 164 deletions
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index b687c57ae7..a4d0733e88 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -34,17 +34,18 @@ namespace { Statistic<> NumSpills("spiller", "Number of register spills"); Statistic<> NumStores("spiller", "Number of stores added"); Statistic<> NumLoads ("spiller", "Number of loads added"); + Statistic<> NumReused("spiller", "Number of values reused"); enum SpillerName { simple, local }; cl::opt<SpillerName> SpillerOpt("spiller", - cl::desc("Spiller to use: (default: simple)"), + cl::desc("Spiller to use: (default: local)"), cl::Prefix, cl::values(clEnumVal(simple, " simple spiller"), clEnumVal(local, " local spiller"), clEnumValEnd), - cl::init(simple)); + cl::init(local)); } //===----------------------------------------------------------------------===// @@ -149,15 +150,15 @@ bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF, E = MBB.end(); MII != E; ++MII) { MachineInstr &MI = *MII; for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { - MachineOperand &MOP = MI.getOperand(i); - if (MOP.isRegister() && MOP.getReg() && - MRegisterInfo::isVirtualRegister(MOP.getReg())){ - unsigned VirtReg = MOP.getReg(); + MachineOperand &MO = MI.getOperand(i); + if (MO.isRegister() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) { + unsigned VirtReg = MO.getReg(); unsigned PhysReg = VRM.getPhys(VirtReg); if (VRM.hasStackSlot(VirtReg)) { int StackSlot = VRM.getStackSlot(VirtReg); - if (MOP.isUse() && + if (MO.isUse() && std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg) == LoadedRegs.end()) { MRI.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot); @@ -166,9 +167,8 @@ bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF, DEBUG(std::cerr << '\t' << *prior(MII)); } - if (MOP.isDef()) { - MRI.storeRegToStackSlot(MBB, next(MII), PhysReg, - VRM.getStackSlot(VirtReg)); + if (MO.isDef()) { + MRI.storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot); ++NumStores; } } @@ -187,186 +187,323 @@ bool SimpleSpiller::runOnMachineFunction(MachineFunction& MF, //===----------------------------------------------------------------------===// namespace { + /// LocalSpiller - This spiller does a simple pass over the machine basic + /// block to attempt to keep spills in registers as much as possible for + /// blocks that have low register pressure (the vreg may be spilled due to + /// register pressure in other blocks). class LocalSpiller : public Spiller { - typedef std::vector<unsigned> Phys2VirtMap; - typedef std::vector<bool> PhysFlag; - typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI; - - MachineFunction *MF; - const TargetMachine *TM; - const TargetInstrInfo *TII; const MRegisterInfo *MRI; - const VirtRegMap *VRM; - Phys2VirtMap p2vMap_; - PhysFlag dirty_; - Virt2MI lastDef_; - + const TargetInstrInfo *TII; public: - bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM); - - private: - void vacateJustPhysReg(MachineBasicBlock& MBB, - MachineBasicBlock::iterator MII, - unsigned PhysReg); - - void vacatePhysReg(MachineBasicBlock& MBB, - MachineBasicBlock::iterator MII, - unsigned PhysReg) { - vacateJustPhysReg(MBB, MII, PhysReg); - for (const unsigned* as = MRI->getAliasSet(PhysReg); *as; ++as) - vacateJustPhysReg(MBB, MII, *as); - } - - void handleUse(MachineBasicBlock& MBB, - MachineBasicBlock::iterator MII, - unsigned VirtReg, - unsigned PhysReg) { - // check if we are replacing a previous mapping - if (p2vMap_[PhysReg] != VirtReg) { - vacatePhysReg(MBB, MII, PhysReg); - p2vMap_[PhysReg] = VirtReg; - // load if necessary - if (VRM->hasStackSlot(VirtReg)) { - MRI->loadRegFromStackSlot(MBB, MII, PhysReg, - VRM->getStackSlot(VirtReg)); - ++NumLoads; - DEBUG(std::cerr << "added: " << *prior(MII)); - lastDef_[VirtReg] = MII; - } - } + bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM) { + MRI = MF.getTarget().getRegisterInfo(); + TII = MF.getTarget().getInstrInfo(); + DEBUG(std::cerr << "\n**** Local spiller rewriting function '" + << MF.getFunction()->getName() << "':\n"); + + for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); + MBB != E; ++MBB) + RewriteMBB(*MBB, VRM); + return true; } - - void handleDef(MachineBasicBlock& MBB, - MachineBasicBlock::iterator MII, - unsigned VirtReg, - unsigned PhysReg) { - // check if we are replacing a previous mapping - if (p2vMap_[PhysReg] != VirtReg) - vacatePhysReg(MBB, MII, PhysReg); - - p2vMap_[PhysReg] = VirtReg; - dirty_[PhysReg] = true; - lastDef_[VirtReg] = MII; - } - - void eliminateVirtRegsInMBB(MachineBasicBlock& MBB); + private: + void RewriteMBB(MachineBasicBlock &MBB, const VirtRegMap &VRM); + void ClobberPhysReg(unsigned PR, std::map<int, unsigned> &SpillSlots, + std::map<unsigned, int> &PhysRegs); + void ClobberPhysRegOnly(unsigned PR, std::map<int, unsigned> &SpillSlots, + std::map<unsigned, int> &PhysRegs); }; } -bool LocalSpiller::runOnMachineFunction(MachineFunction &mf, - const VirtRegMap &vrm) { - MF = &mf; - TM = &MF->getTarget(); - TII = TM->getInstrInfo(); - MRI = TM->getRegisterInfo(); - VRM = &vrm; - p2vMap_.assign(MRI->getNumRegs(), 0); - dirty_.assign(MRI->getNumRegs(), false); +void LocalSpiller::ClobberPhysRegOnly(unsigned PhysReg, + std::map<int, unsigned> &SpillSlots, + std::map<unsigned, int> &PhysRegs) { + std::map<unsigned, int>::iterator I = PhysRegs.find(PhysReg); + if (I != PhysRegs.end()) { + int Slot = I->second; + PhysRegs.erase(I); + assert(SpillSlots[Slot] == PhysReg && "Bidirectional map mismatch!"); + SpillSlots.erase(Slot); + DEBUG(std::cerr << "PhysReg " << MRI->getName(PhysReg) + << " clobbered, invalidating SS#" << Slot << "\n"); - DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); - DEBUG(std::cerr << "********** Function: " - << MF->getFunction()->getName() << '\n'); - - for (MachineFunction::iterator MBB = MF->begin(), E = MF->end(); - MBB != E; ++MBB) { - lastDef_.grow(MF->getSSARegMap()->getLastVirtReg()); - DEBUG(std::cerr << MBB->getBasicBlock()->getName() << ":\n"); - eliminateVirtRegsInMBB(*MBB); - // clear map, dirty flag and last ref - p2vMap_.assign(p2vMap_.size(), 0); - dirty_.assign(dirty_.size(), false); - lastDef_.clear(); } - return true; } -void LocalSpiller::vacateJustPhysReg(MachineBasicBlock& MBB, - MachineBasicBlock::iterator MII, - unsigned PhysReg) { - unsigned VirtReg = p2vMap_[PhysReg]; - if (dirty_[PhysReg] && VRM->hasStackSlot(VirtReg)) { - assert(lastDef_[VirtReg] && "virtual register is mapped " - "to a register and but was not defined!"); - MachineBasicBlock::iterator lastDef = lastDef_[VirtReg]; - MachineBasicBlock::iterator nextLastRef = next(lastDef); - MRI->storeRegToStackSlot(*lastDef->getParent(), - nextLastRef, - PhysReg, - VRM->getStackSlot(VirtReg)); - ++NumStores; - DEBUG(std::cerr << "added: " << *prior(nextLastRef); - std::cerr << "after: " << *lastDef); - lastDef_[VirtReg] = 0; - } - p2vMap_[PhysReg] = 0; - dirty_[PhysReg] = false; +void LocalSpiller::ClobberPhysReg(unsigned PhysReg, + std::map<int, unsigned> &SpillSlots, + std::map<unsigned, int> &PhysRegs) { + for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) + ClobberPhysRegOnly(*AS, SpillSlots, PhysRegs); + ClobberPhysRegOnly(PhysReg, SpillSlots, PhysRegs); } -void LocalSpiller::eliminateVirtRegsInMBB(MachineBasicBlock &MBB) { - for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end(); - MI != E; ++MI) { - - // if we have references to memory operands make sure - // we clear all physical registers that may contain - // the value of the spilled virtual register - VirtRegMap::MI2VirtMapTy::const_iterator i, e; - for (tie(i, e) = VRM->getFoldedVirts(MI); i != e; ++i) { - if (VRM->hasPhys(i->second)) - vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second)); - } - // rewrite all used operands - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& op = MI->getOperand(i); - if (op.isRegister() && op.getReg() && op.isUse() && - MRegisterInfo::isVirtualRegister(op.getReg())) { - unsigned VirtReg = op.getReg(); - unsigned PhysReg = VRM->getPhys(VirtReg); - handleUse(MBB, MI, VirtReg, PhysReg); - MI->SetMachineOperandReg(i, PhysReg); - // mark as dirty if this is def&use - if (op.isDef()) { - dirty_[PhysReg] = true; - lastDef_[VirtReg] = MI; +// ReusedOp - For each reused operand, we keep track of a bit of information, in +// case we need to rollback upon processing a new operand. See comments below. +namespace { + struct ReusedOp { + // The MachineInstr operand that reused an available value. + unsigned Operand; + + // StackSlot - The spill slot of the value being reused. + unsigned StackSlot; + + // PhysRegReused - The physical register the value was available in. + unsigned PhysRegReused; + + // AssignedPhysReg - The physreg that was assigned for use by the reload. + unsigned AssignedPhysReg; + + ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr) + : Operand(o), StackSlot(ss), PhysRegReused(prr), AssignedPhysReg(apr) {} + }; +} + + +/// rewriteMBB - Keep track of which spills are available even after the +/// register allocator is done with them. If possible, avoid reloading vregs. +void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, const VirtRegMap &VRM) { + + // SpillSlotsAvailable - This map keeps track of all of the spilled virtual + // register values that are still available, due to being loaded to stored to, + // but not invalidated yet. + std::map<int, unsigned> SpillSlotsAvailable; + + // PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating + // which physregs are in use holding a stack slot value. + std::map<unsigned, int> PhysRegsAvailable; + + DEBUG(std::cerr << MBB.getBasicBlock()->getName() << ":\n"); + + std::vector<ReusedOp> ReusedOperands; + + // DefAndUseVReg - When we see a def&use operand that is spilled, keep track + // of it. ".first" is the machine operand index (should always be 0 for now), + // and ".second" is the virtual register that is spilled. + std::vector<std::pair<unsigned, unsigned> > DefAndUseVReg; + + for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); + MII != E; ) { + MachineInstr &MI = *MII; + MachineBasicBlock::iterator NextMII = MII; ++NextMII; + + ReusedOperands.clear(); + DefAndUseVReg.clear(); + + // Process all of the spilled uses and all non spilled reg references. + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (MO.isRegister() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) { + unsigned VirtReg = MO.getReg(); + + if (!VRM.hasStackSlot(VirtReg)) { + // This virtual register was assigned a physreg! + MI.SetMachineOperandReg(i, VRM.getPhys(VirtReg)); + } else { + // Is this virtual register a spilled value? + if (MO.isUse()) { + int StackSlot = VRM.getStackSlot(VirtReg); + unsigned PhysReg; + + // Check to see if this stack slot is available. + std::map<int, unsigned>::iterator SSI = + SpillSlotsAvailable.find(StackSlot); + if (SSI != SpillSlotsAvailable.end()) { + // If this stack slot value is already available, reuse it! + PhysReg = SSI->second; + MI.SetMachineOperandReg(i, PhysReg); + DEBUG(std::cerr << "Reusing SS#" << StackSlot << " from physreg " + << MRI->getName(SSI->second) << "\n"); + + // The only technical detail we have is that we don't know that + // PhysReg won't be clobbered by a reloaded stack slot that occurs + // later in the instruction. In particular, consider 'op V1, V2'. + // If V1 is available in physreg R0, we would choose to reuse it + // here, instead of reloading it into the register the allocator + // indicated (say R1). However, V2 might have to be reloaded + // later, and it might indicate that it needs to live in R0. When + // this occurs, we need to have information available that + // indicates it is safe to use R1 for the reload instead of R0. + // + // To further complicate matters, we might conflict with an alias, + // or R0 and R1 might not be compatible with each other. In this + // case, we actually insert a reload for V1 in R1, ensuring that + // we can get at R0 or its alias. + ReusedOperands.push_back(ReusedOp(i, StackSlot, PhysReg, + VRM.getPhys(VirtReg))); + ++NumReused; + } else { + // Otherwise, reload it and remember that we have it. + PhysReg = VRM.getPhys(VirtReg); + + // Note that, if we reused a register for a previous operand, the + // register we want to reload into might not actually be + // available. If this occurs, use the register indicated by the + // reuser. + if (!ReusedOperands.empty()) // This is most often empty. + for (unsigned ro = 0, e = ReusedOperands.size(); ro != e; ++ro) + if (ReusedOperands[ro].PhysRegReused == PhysReg) { + // Yup, use the reload register that we didn't use before. + PhysReg = ReusedOperands[ro].AssignedPhysReg; + break; + } else { + ReusedOp &Op = ReusedOperands[ro]; + unsigned PRRU = Op.PhysRegReused; + for (const unsigned *AS = MRI->getAliasSet(PRRU); *AS; ++AS) + if (*AS == PhysReg) { + // Okay, we found out that an alias of a reused register + // was used. This isn't good because it means we have + // to undo a previous reuse. + MRI->loadRegFromStackSlot(MBB, &MI, Op.AssignedPhysReg, + Op.StackSlot); + ClobberPhysReg(Op.AssignedPhysReg, SpillSlotsAvailable, + PhysRegsAvailable); + + MI.SetMachineOperandReg(Op.Operand, Op.AssignedPhysReg); + PhysRegsAvailable[Op.AssignedPhysReg] = Op.StackSlot; + SpillSlotsAvailable[Op.StackSlot] = Op.AssignedPhysReg; + PhysRegsAvailable.erase(Op.PhysRegReused); + DEBUG(std::cerr << "Remembering SS#" << Op.StackSlot + << " in physreg " + << MRI->getName(Op.AssignedPhysReg) << "\n"); + ++NumLoads; + DEBUG(std::cerr << '\t' << *prior(MII)); + + DEBUG(std::cerr << "Reuse undone!\n"); + ReusedOperands.erase(ReusedOperands.begin()+ro); + --NumReused; + goto ContinueReload; + } + } + ContinueReload: + + MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot); + // This invalidates PhysReg. + ClobberPhysReg(PhysReg, SpillSlotsAvailable, PhysRegsAvailable); + + MI.SetMachineOperandReg(i, PhysReg); + PhysRegsAvailable[PhysReg] = StackSlot; + SpillSlotsAvailable[StackSlot] = PhysReg; + DEBUG(std::cerr << "Remembering SS#" << StackSlot <<" in physreg " + << MRI->getName(PhysReg) << "\n"); + ++NumLoads; + DEBUG(std::cerr << '\t' << *prior(MII)); + } + + // If this is both a def and a use, we need to emit a store to the + // stack slot after the instruction. Keep track of D&U operands + // because we already changed it to a physreg here. + if (MO.isDef()) { + // Remember that this was a def-and-use operand, and that the + // stack slot is live after this instruction executes. + DefAndUseVReg.push_back(std::make_pair(i, VirtReg)); + } + } } } } - // spill implicit physical register defs - const TargetInstrDescriptor& tid = TII->get(MI->getOpcode()); - for (const unsigned* id = tid.ImplicitDefs; *id; ++id) - vacatePhysReg(MBB, MI, *id); - - // spill explicit physical register defs - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& op = MI->getOperand(i); - if (op.isRegister() && op.getReg() && !op.isUse() && - MRegisterInfo::isPhysicalRegister(op.getReg())) - vacatePhysReg(MBB, MI, op.getReg()); + // Loop over all of the implicit defs, clearing them from our available + // sets. + const TargetInstrDescriptor &InstrDesc = TII->get(MI.getOpcode()); + for (const unsigned* ImpDef = InstrDesc.ImplicitDefs; *ImpDef; ++ImpDef) + ClobberPhysReg(*ImpDef, SpillSlotsAvailable, PhysRegsAvailable); + + DEBUG(std::cerr << '\t' << MI); + + // If we have folded references to memory operands, make sure we clear all + // physical registers that may contain the value of the spilled virtual + // register + VirtRegMap::MI2VirtMapTy::const_iterator I, E; + for (tie(I, E) = VRM.getFoldedVirts(&MI); I != E; ++I) { + DEBUG(std::cerr << "Folded vreg: " << I->second); + if (VRM.hasStackSlot(I->second)) { + int SS = VRM.getStackSlot(I->second); + DEBUG(std::cerr << " - StackSlot: " << SS << "\n"); + + std::map<int, unsigned>::iterator I = SpillSlotsAvailable.find(SS); + if (I != SpillSlotsAvailable.end()) { + PhysRegsAvailable.erase(I->second); + SpillSlotsAvailable.erase(I); + } + } else { + DEBUG(std::cerr << ": No stack slot!\n"); + } } - // rewrite def operands (def&use was handled with the - // uses so don't check for those here) - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand& op = MI->getOperand(i); - if (op.isRegister() && op.getReg() && !op.isUse()) - if (MRegisterInfo::isPhysicalRegister(op.getReg())) - vacatePhysReg(MBB, MI, op.getReg()); - else { - unsigned PhysReg = VRM->getPhys(op.getReg()); - handleDef(MBB, MI, op.getReg(), PhysReg); - MI->SetMachineOperandReg(i, PhysReg); + // Process all of the spilled defs. + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (MO.isRegister() && MO.getReg() && MO.isDef()) { + unsigned VirtReg = MO.getReg(); + + bool TakenCareOf = false; + if (!MRegisterInfo::isVirtualRegister(VirtReg)) { + // Check to see if this is a def-and-use vreg operand that we do need + // to insert a store for. + bool OpTakenCareOf = false; + if (MO.isUse() && !DefAndUseVReg.empty()) { + for (unsigned dau = 0, e = DefAndUseVReg.size(); dau != e; ++dau) + if (DefAndUseVReg[dau].first == i) { + VirtReg = DefAndUseVReg[dau].second; + OpTakenCareOf = true; + break; + } + } + + if (!OpTakenCareOf) { + ClobberPhysReg(VirtReg, SpillSlotsAvailable, PhysRegsAvailable); + TakenCareOf = true; + } + } + + if (!TakenCareOf) { + // The only vregs left are stack slot definitions. + int StackSlot = VRM.getStackSlot(VirtReg); + unsigned PhysReg; + + // If this is a def&use operand, and we used a different physreg for + // it than the one assigned, make sure to execute the store from the + // correct physical register. + if (MO.getReg() == VirtReg) + PhysReg = VRM.getPhys(VirtReg); + else + PhysReg = MO.getReg(); + + MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot); + DEBUG(std::cerr << "Store:\t" << *next(MII)); + MI.SetMachineOperandReg(i, PhysReg); + + // If the stack slot value was previously available in some other + // register, change it now. Otherwise, make the register available, + // in PhysReg. + std::map<int, unsigned>::iterator SSA = + SpillSlotsAvailable.find(StackSlot); + if (SSA != SpillSlotsAvailable.end()) { + // Remove the record for physreg. + PhysRegsAvailable.erase(SSA->second); + SpillSlotsAvailable.erase(SSA); + } + ClobberPhysReg(PhysReg, SpillSlotsAvailable, PhysRegsAvailable); + + PhysRegsAvailable[PhysReg] = StackSlot; + SpillSlotsAvailable[StackSlot] = PhysReg; + DEBUG(std::cerr << "Updating SS#" << StackSlot <<" in physreg " + << MRI->getName(PhysReg) << "\n"); + + ++NumStores; + VirtReg = PhysReg; } + } } - - DEBUG(std::cerr << '\t' << *MI); + MII = NextMII; } - - for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i) - vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i); } + llvm::Spiller* llvm::createSpiller() { switch (SpillerOpt) { default: assert(0 && "Unreachable!"); |