diff options
author | Evan Cheng <evan.cheng@apple.com> | 2009-04-21 22:46:52 +0000 |
---|---|---|
committer | Evan Cheng <evan.cheng@apple.com> | 2009-04-21 22:46:52 +0000 |
commit | 5b69ebac857104770b1a751bf7a463fda4330a62 (patch) | |
tree | 4f04dd784d95779528ce075c994f65335631067c /lib/CodeGen | |
parent | 578ccf81e5b94965e3ce8b4eadb6834e39f5f41d (diff) | |
download | external_llvm-5b69ebac857104770b1a751bf7a463fda4330a62.zip external_llvm-5b69ebac857104770b1a751bf7a463fda4330a62.tar.gz external_llvm-5b69ebac857104770b1a751bf7a463fda4330a62.tar.bz2 |
It has finally happened. Spiller is now using live interval info.
This fixes a very subtle bug. vr defined by an implicit_def is allowed overlap with any register since it doesn't actually modify anything. However, if it's used as a two-address use, its live range can be extended and it can be spilled. The spiller must take care not to emit a reload for the vn number that's defined by the implicit_def. This is both a correctness and performance issue.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69743 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen')
-rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 6 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 2 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocPBQP.cpp | 2 | ||||
-rw-r--r-- | lib/CodeGen/Spiller.cpp | 85 | ||||
-rw-r--r-- | lib/CodeGen/Spiller.h | 13 |
5 files changed, 68 insertions, 40 deletions
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index f6a1c48..6691c2e 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1304,7 +1304,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, // Update stack slot spill weight if we are splitting. float Weight = getSpillWeight(HasDef, HasUse, loopDepth); - if (!TrySplit) + if (!TrySplit) SSWeight += Weight; // Create a new virtual register for the spill interval. @@ -1338,7 +1338,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, HasUse = false; HasDef = false; CanFold = false; - if (isRemoved(MI)) { + if (isNotInMIMap(MI)) { SSWeight -= Weight; break; } @@ -1393,7 +1393,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, if (DefIsReMat && ImpUse) MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); - // create a new register interval for this spill / remat. + // Create a new register interval for this spill / remat. LiveInterval &nI = getOrCreateInterval(NewVReg); if (CreatedNewVReg) { NewLIs.push_back(&nI); diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index c738315..2e65b3f 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -345,7 +345,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { linearScan(); // Rewrite spill code and update the PhysRegsUsed set. - spiller_->runOnMachineFunction(*mf_, *vrm_); + spiller_->runOnMachineFunction(*mf_, *vrm_, li_); assert(unhandled_.empty() && "Unhandled live intervals remain!"); fixed_.clear(); diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index adab2b0..748fae4 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -854,7 +854,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { // Run spiller std::auto_ptr<Spiller> spiller(createSpiller()); - spiller->runOnMachineFunction(*mf, *vrm); + spiller->runOnMachineFunction(*mf, *vrm, lis); return true; } diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp index 92bb785..26366d6 100644 --- a/lib/CodeGen/Spiller.cpp +++ b/lib/CodeGen/Spiller.cpp @@ -23,6 +23,7 @@ STATISTIC(NumDRM , "Number of re-materializable defs elided"); STATISTIC(NumStores , "Number of stores added"); STATISTIC(NumPSpills , "Number of physical register spills"); STATISTIC(NumOmitted , "Number of reloads omited"); +STATISTIC(NumAvoided , "Number of reloads deemed unnecessary"); STATISTIC(NumCopified, "Number of available reloads turned into copies"); STATISTIC(NumReMats , "Number of re-materialization"); STATISTIC(NumLoads , "Number of loads added"); @@ -50,7 +51,8 @@ SpillerOpt("spiller", Spiller::~Spiller() {} -bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { +bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM, + LiveIntervals* LIs) { DOUT << "********** REWRITE MACHINE CODE **********\n"; DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; const TargetMachine &TM = MF.getTarget(); @@ -521,7 +523,8 @@ unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI, // Local Spiller Implementation // // ***************************** // -bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { +bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM, + LiveIntervals* LIs) { RegInfo = &MF.getRegInfo(); TRI = MF.getTarget().getRegisterInfo(); TII = MF.getTarget().getInstrInfo(); @@ -555,7 +558,7 @@ bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { DFI != E; ++DFI) { MachineBasicBlock *MBB = *DFI; if (!EarlyVisited.count(MBB)) - RewriteMBB(*MBB, VRM, Spills, RegKills, KillOps); + RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps); // If this MBB is the only predecessor of a successor. Keep the // availability information and visit it next. @@ -571,7 +574,7 @@ bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { MBB = SinglePredSuccs[0]; if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) { Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps); - RewriteMBB(*MBB, VRM, Spills, RegKills, KillOps); + RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps); } } } while (MBB); @@ -1109,6 +1112,7 @@ void LocalSpiller::TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist, /// 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, + LiveIntervals *LIs, AvailableSpills &Spills, BitVector &RegKills, std::vector<MachineOperand*> &KillOps) { DOUT << "\n**** Local spiller rewriting MBB '" @@ -1339,6 +1343,22 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM, if (!MO.isUse()) continue; // Handle defs in the loop below (handle use&def here though) + bool AvoidReload = false; + if (LIs->hasInterval(VirtReg)) { + LiveInterval &LI = LIs->getInterval(VirtReg); + if (!LI.liveAt(LIs->getUseIndex(LI.beginNumber()))) + // Must be defined by an implicit def. It should not be spilled. Note, + // this is for correctness reason. e.g. + // 8 %reg1024<def> = IMPLICIT_DEF + // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 + // The live range [12, 14) are not part of the r1024 live interval since + // it's defined by an implicit def. It will not conflicts with live + // interval of r1025. Now suppose both registers are spilled, you can + // easily see a situation where both registers are reloaded before + // the INSERT_SUBREG and both target registers that would overlap. + AvoidReload = true; + } + bool DoReMat = VRM.isReMaterialized(VirtReg); int SSorRMId = DoReMat ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg); @@ -1357,14 +1377,14 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM, // = EXTRACT_SUBREG fi#1 // fi#1 is available in EDI, but it cannot be reused because it's not in // the right register file. - if (PhysReg && + if (PhysReg && !AvoidReload && (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) { const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); if (!RC->contains(PhysReg)) PhysReg = 0; } - if (PhysReg) { + if (PhysReg && !AvoidReload) { // This spilled operand might be part of a two-address operand. If this // is the case, then changing it will necessarily require changing the // def part of the instruction as well. However, in some cases, we @@ -1513,34 +1533,39 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM, RegInfo->setPhysRegUsed(PhysReg); ReusedOperands.markClobbered(PhysReg); - if (DoReMat) { - ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM); - } else { - const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); - TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC); - MachineInstr *LoadMI = prior(MII); - VRM.addSpillSlotUse(SSorRMId, LoadMI); - ++NumLoads; - } - // This invalidates PhysReg. - Spills.ClobberPhysReg(PhysReg); - - // Any stores to this stack slot are not dead anymore. - if (!DoReMat) - MaybeDeadStores[SSorRMId] = NULL; - Spills.addAvailable(SSorRMId, PhysReg); - // Assumes this is the last use. IsKill will be unset if reg is reused - // unless it's a two-address operand. - if (!MI.isRegTiedToDefOperand(i) && - KilledMIRegs.count(VirtReg) == 0) { - MI.getOperand(i).setIsKill(); - KilledMIRegs.insert(VirtReg); + if (AvoidReload) + ++NumAvoided; + else { + if (DoReMat) { + ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM); + } else { + const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); + TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC); + MachineInstr *LoadMI = prior(MII); + VRM.addSpillSlotUse(SSorRMId, LoadMI); + ++NumLoads; + } + // This invalidates PhysReg. + Spills.ClobberPhysReg(PhysReg); + + // Any stores to this stack slot are not dead anymore. + if (!DoReMat) + MaybeDeadStores[SSorRMId] = NULL; + Spills.addAvailable(SSorRMId, PhysReg); + // Assumes this is the last use. IsKill will be unset if reg is reused + // unless it's a two-address operand. + if (!MI.isRegTiedToDefOperand(i) && + KilledMIRegs.count(VirtReg) == 0) { + MI.getOperand(i).setIsKill(); + KilledMIRegs.insert(VirtReg); + } + + UpdateKills(*prior(MII), RegKills, KillOps, TRI); + DOUT << '\t' << *prior(MII); } unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg; MI.getOperand(i).setReg(RReg); MI.getOperand(i).setSubReg(0); - UpdateKills(*prior(MII), RegKills, KillOps, TRI); - DOUT << '\t' << *prior(MII); } // Ok - now we can remove stores that have been confirmed dead. diff --git a/lib/CodeGen/Spiller.h b/lib/CodeGen/Spiller.h index c0d0837..f00831f 100644 --- a/lib/CodeGen/Spiller.h +++ b/lib/CodeGen/Spiller.h @@ -17,6 +17,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Streams.h" #include "llvm/Function.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -37,8 +38,8 @@ namespace llvm { /// virtual registers to stack slots, rewriting the code. struct Spiller { virtual ~Spiller(); - virtual bool runOnMachineFunction(MachineFunction &MF, - VirtRegMap &VRM) = 0; + virtual bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM, + LiveIntervals* LIs) = 0; }; /// createSpiller - Create an return a spiller object, as specified on the @@ -49,7 +50,8 @@ namespace llvm { // Simple Spiller Implementation struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller { - bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM); + bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM, + LiveIntervals* LIs); }; // ************************************************************************ // @@ -287,7 +289,8 @@ namespace llvm { BitVector AllocatableRegs; DenseMap<MachineInstr*, unsigned> DistanceMap; public: - bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM); + bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM, + LiveIntervals* LI); private: void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist, unsigned Reg, BitVector &RegKills, @@ -329,7 +332,7 @@ namespace llvm { VirtRegMap &VRM); void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM, - AvailableSpills &Spills, + LiveIntervals *LIs, AvailableSpills &Spills, BitVector &RegKills, std::vector<MachineOperand*> &KillOps); }; } |