X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FExecutionDepsFix.cpp;h=031f19c135a97df9a81c83ad9f5f73e0a6e24031;hb=6a2f9b91379140c36a11ade6c0673bd7490eba32;hp=d094411116d4ca432a2c9fec5de4b164508cf486;hpb=2947f730a96fc602ea008bba1929ae4f0638850a;p=oota-llvm.git diff --git a/lib/CodeGen/ExecutionDepsFix.cpp b/lib/CodeGen/ExecutionDepsFix.cpp index d094411116d..031f19c135a 100644 --- a/lib/CodeGen/ExecutionDepsFix.cpp +++ b/lib/CodeGen/ExecutionDepsFix.cpp @@ -21,15 +21,16 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "execution-fix" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/CodeGen/LiveRegUnits.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" using namespace llvm; /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track @@ -59,7 +60,7 @@ struct DomainValue { // Pointer to the next DomainValue in a chain. When two DomainValues are // merged, Victim.Next is set to point to Victor, so old DomainValue - // references can be updated by folowing the chain. + // references can be updated by following the chain. DomainValue *Next; // Twiddleable instructions using or defining these registers. @@ -91,7 +92,7 @@ struct DomainValue { // First domain available. unsigned getFirstDomain() const { - return CountTrailingZeros_32(AvailableDomains); + return countTrailingZeros(AvailableDomains); } DomainValue() : Refs(0) { clear(); } @@ -136,6 +137,12 @@ class ExeDepsFix : public MachineFunctionPass { typedef DenseMap LiveOutMap; LiveOutMap LiveOuts; + /// List of undefined register reads in this block in forward order. + std::vector > UndefReads; + + /// Storage for register unit liveness. + LiveRegUnits LiveUnits; + /// Current instruction number. /// The first instruction in each basic block is 0. int CurInstr; @@ -185,6 +192,8 @@ private: void processDefs(MachineInstr*, bool Kill); void visitSoftInstr(MachineInstr*, unsigned mask); void visitHardInstr(MachineInstr*, unsigned domain); + bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref); + void processUndefReads(MachineBasicBlock*); }; } @@ -341,6 +350,10 @@ void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) { // Reset instruction counter in each basic block. CurInstr = 0; + // Set up UndefReads to track undefined register reads. + UndefReads.clear(); + LiveUnits.clear(); + // Set up LiveRegs to represent registers entering MBB. if (!LiveRegs) LiveRegs = new LiveReg[NumRegs]; @@ -448,13 +461,49 @@ void ExeDepsFix::visitInstr(MachineInstr *MI) { processDefs(MI, !DomP.first); } +/// \brief Return true to if it makes sense to break dependence on a partial def +/// or undef use. +bool ExeDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx, + unsigned Pref) { + int rx = regIndex(MI->getOperand(OpIdx).getReg()); + if (rx < 0) + return false; + + unsigned Clearance = CurInstr - LiveRegs[rx].Def; + DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); + + if (Pref > Clearance) { + DEBUG(dbgs() << ": Break dependency.\n"); + return true; + } + // The current clearance seems OK, but we may be ignoring a def from a + // back-edge. + if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) { + DEBUG(dbgs() << ": OK .\n"); + return false; + } + // A def from an unprocessed back-edge may make us break this dependency. + DEBUG(dbgs() << ": Wait for back-edge to resolve.\n"); + return false; +} + // Update def-ages for registers defined by MI. // If Kill is set, also kill off DomainValues clobbered by the defs. +// +// Also break dependencies on partial defs and undef uses. void ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) { assert(!MI->isDebugValue() && "Won't process debug values"); + + // Break dependence on undef uses. Do this before updating LiveRegs below. + unsigned OpNum; + unsigned Pref = TII->getUndefRegClearance(MI, OpNum, TRI); + if (Pref) { + if (shouldBreakDependence(MI, OpNum, Pref)) + UndefReads.push_back(std::make_pair(MI, OpNum)); + } const MCInstrDesc &MCID = MI->getDesc(); for (unsigned i = 0, - e = MCID.isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); + e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) @@ -471,16 +520,60 @@ void ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) { DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr << '\t' << *MI); + // Check clearance before partial register updates. + // Call breakDependence before setting LiveRegs[rx].Def. + unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI); + if (Pref && shouldBreakDependence(MI, i, Pref)) + TII->breakPartialRegDependency(MI, i, TRI); + + // How many instructions since rx was last written? LiveRegs[rx].Def = CurInstr; // Kill off domains redefined by generic instructions. if (Kill) kill(rx); } - ++CurInstr; } +/// \break Break false dependencies on undefined register reads. +/// +/// Walk the block backward computing precise liveness. This is expensive, so we +/// only do it on demand. Note that the occurrence of undefined register reads +/// that should be broken is very rare, but when they occur we may have many in +/// a single block. +void ExeDepsFix::processUndefReads(MachineBasicBlock *MBB) { + if (UndefReads.empty()) + return; + + // Collect this block's live out register units. + LiveUnits.init(TRI); + for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) { + LiveUnits.addLiveIns(*SI, *TRI); + } + MachineInstr *UndefMI = UndefReads.back().first; + unsigned OpIdx = UndefReads.back().second; + + for (MachineBasicBlock::reverse_iterator I = MBB->rbegin(), E = MBB->rend(); + I != E; ++I) { + // Update liveness, including the current instrucion's defs. + LiveUnits.stepBackward(*I, *TRI); + + if (UndefMI == &*I) { + if (!LiveUnits.contains(UndefMI->getOperand(OpIdx).getReg(), *TRI)) + TII->breakPartialRegDependency(UndefMI, OpIdx, TRI); + + UndefReads.pop_back(); + if (UndefReads.empty()) + return; + + UndefMI = UndefReads.back().first; + OpIdx = UndefReads.back().second; + } + } +} + // A hard instruction only works in one domain. All input registers will be // forced into that domain. void ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) { @@ -526,7 +619,7 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { // Is it possible to use this collapsed register for free? if (dv->isCollapsed()) { // Restrict available domains to the ones in common with the operand. - // If there are no common domains, we must pay the cross-domain + // If there are no common domains, we must pay the cross-domain // penalty for this operand. if (common) available = common; } else if (common) @@ -541,7 +634,7 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { // If the collapsed operands force a single domain, propagate the collapse. if (isPowerOf2_32(available)) { - unsigned domain = CountTrailingZeros_32(available); + unsigned domain = countTrailingZeros(available); TII->setExecutionDomain(mi, domain); visitHardInstr(mi, domain); return; @@ -550,7 +643,7 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { // Kill off any remaining uses that don't match available, and build a list of // incoming DomainValues that we want to merge. SmallVector Regs; - for (SmallVector::iterator i=used.begin(), e=used.end(); i!=e; ++i) { + for (SmallVectorImpl::iterator i=used.begin(), e=used.end(); i!=e; ++i) { int rx = *i; const LiveReg &LR = LiveRegs[rx]; // This useless DomainValue could have been missed above. @@ -560,7 +653,7 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { } // Sorted insertion. bool Inserted = false; - for (SmallVector::iterator i = Regs.begin(), e = Regs.end(); + for (SmallVectorImpl::iterator i = Regs.begin(), e = Regs.end(); i != e && !Inserted; ++i) { if (LR.Def < i->Def) { Inserted = true; @@ -577,6 +670,9 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { while (!Regs.empty()) { if (!dv) { dv = Regs.pop_back_val().Value; + // Force the first dv to match the current instruction. + dv->AvailableDomains = dv->getCommonDomains(available); + assert(dv->AvailableDomains && "Domain should have been filtered"); continue; } @@ -588,20 +684,24 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { continue; // If latest didn't merge, it is useless now. Kill all registers using it. - for (SmallVector::iterator i=used.begin(), e=used.end(); i != e; ++i) + for (SmallVectorImpl::iterator i=used.begin(), e=used.end(); i!=e; ++i) if (LiveRegs[*i].Value == Latest) kill(*i); } // dv is the DomainValue we are going to use for this instruction. - if (!dv) + if (!dv) { dv = alloc(); - dv->AvailableDomains = available; + dv->AvailableDomains = available; + } dv->Instrs.push_back(mi); - // Finally set all defs and non-collapsed uses to dv. - for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) { - MachineOperand &mo = mi->getOperand(i); + // Finally set all defs and non-collapsed uses to dv. We must iterate through + // all the operators, including imp-def ones. + for (MachineInstr::mop_iterator ii = mi->operands_begin(), + ee = mi->operands_end(); + ii != ee; ++ii) { + MachineOperand &mo = *ii; if (!mo.isReg()) continue; int rx = regIndex(mo.getReg()); if (rx < 0) continue; @@ -639,7 +739,8 @@ bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { // or -1. AliasMap.resize(TRI->getNumRegs(), -1); for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i) - for (const unsigned *AI = TRI->getOverlaps(RC->getRegister(i)); *AI; ++AI) + for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); + AI.isValid(); ++AI) AliasMap[*AI] = i; } @@ -655,6 +756,7 @@ bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) visitInstr(I); + processUndefReads(MBB); leaveBasicBlock(MBB); } @@ -663,6 +765,11 @@ bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { for (unsigned i = 0, e = Loops.size(); i != e; ++i) { MachineBasicBlock *MBB = Loops[i]; enterBasicBlock(MBB); + for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; + ++I) + if (!I->isDebugValue()) + processDefs(I, false); + processUndefReads(MBB); leaveBasicBlock(MBB); } @@ -678,6 +785,7 @@ bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { delete[] FI->second; } LiveOuts.clear(); + UndefReads.clear(); Avail.clear(); Allocator.DestroyAll();