From 7a0f1851ec0ac25d94cebc06f8f611a48e5f4326 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Tue, 20 May 2008 08:13:21 +0000 Subject: More local spiller complexity! If local spiller optimization turns some instruction into an identity copy, it will be removed. If the output register happens to be dead (and source is obviously killed), transfer the kill / dead information to last use / def in the same MBB. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51306 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/VirtRegMap.cpp | 62 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) (limited to 'lib/CodeGen/VirtRegMap.cpp') diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index 609e12d..3793af0 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -302,6 +302,7 @@ namespace { MachineRegisterInfo *RegInfo; const TargetRegisterInfo *TRI; const TargetInstrInfo *TII; + DenseMap DistanceMap; public: bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { RegInfo = &MF.getRegInfo(); @@ -333,6 +334,9 @@ namespace { return true; } private: + void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist, + unsigned Reg, BitVector &RegKills, + std::vector &KillOps); bool PrepForUnfoldOpti(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MII, std::vector &MaybeDeadStores, @@ -943,6 +947,7 @@ bool LocalSpiller::PrepForUnfoldOpti(MachineBasicBlock &MBB, VRM.assignVirt2Phys(UnfoldVR, UnfoldPR); VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef); MII = MBB.insert(MII, FoldedMI); + InvalidateKills(MI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); return true; @@ -1026,6 +1031,49 @@ void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB, ++NumStores; } +/// TransferDeadness - A identity copy definition is dead and it's being +/// removed. Find the last def or use and mark it as dead / kill. +void LocalSpiller::TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist, + unsigned Reg, BitVector &RegKills, + std::vector &KillOps) { + int LastUDDist = -1; + MachineInstr *LastUDMI = NULL; + for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg), + RE = RegInfo->reg_end(); RI != RE; ++RI) { + MachineInstr *UDMI = &*RI; + if (UDMI->getParent() != MBB) + continue; + DenseMap::iterator DI = DistanceMap.find(UDMI); + if (DI == DistanceMap.end() || DI->second > CurDist) + continue; + if ((int)DI->second < LastUDDist) + continue; + LastUDDist = DI->second; + LastUDMI = UDMI; + } + + if (LastUDMI) { + const TargetInstrDesc &TID = LastUDMI->getDesc(); + MachineOperand *LastUD = NULL; + for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = LastUDMI->getOperand(i); + if (!MO.isRegister() || MO.getReg() != Reg) + continue; + if (!LastUD || (LastUD->isUse() && MO.isDef())) + LastUD = &MO; + if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) + return; + } + if (LastUD->isDef()) + LastUD->setIsDead(); + else { + LastUD->setIsKill(); + RegKills.set(Reg); + KillOps[Reg] = LastUD; + } + } +} + /// rewriteMBB - Keep track of which spills are available even after the /// register allocator is done with them. If possible, avid reloading vregs. void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { @@ -1054,6 +1102,8 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { std::vector KillOps; KillOps.resize(TRI->getNumRegs(), NULL); + unsigned Dist = 0; + DistanceMap.clear(); for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); MII != E; ) { MachineBasicBlock::iterator NextMII = MII; ++NextMII; @@ -1431,6 +1481,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { InvalidateKill(InReg, RegKills, KillOps); } + InvalidateKills(MI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); Erased = true; @@ -1442,6 +1493,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (PhysReg && TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) { MBB.insert(MII, NewMIs[0]); + InvalidateKills(MI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); Erased = true; @@ -1476,6 +1528,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { NewStore = NewMIs[1]; MBB.insert(MII, NewStore); VRM.addSpillSlotUse(SS, NewStore); + InvalidateKills(MI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); Erased = true; @@ -1549,6 +1602,13 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { ++NumDCE; DOUT << "Removing now-noop copy: " << MI; + SmallVector KillRegs; + InvalidateKills(MI, RegKills, KillOps, &KillRegs); + if (MO.isDead() && !KillRegs.empty()) { + assert(KillRegs[0] == Dst); + // Last def is now dead. + TransferDeadness(&MBB, Dist, Src, RegKills, KillOps); + } VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); Erased = true; @@ -1626,6 +1686,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { ++NumDCE; DOUT << "Removing now-noop copy: " << MI; + InvalidateKills(MI, RegKills, KillOps); VRM.RemoveMachineInstrFromMaps(&MI); MBB.erase(&MI); Erased = true; @@ -1636,6 +1697,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { } } ProcessNextInst: + DistanceMap.insert(std::make_pair(&MI, Dist++)); if (!Erased && !BackTracked) { for (MachineBasicBlock::iterator II = MI; II != NextMII; ++II) UpdateKills(*II, RegKills, KillOps); -- cgit v1.1