X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FX86%2FSSEDomainFix.cpp;h=13680c592e01b274dbfca95729fa68147ba43598;hb=c146c4d47a7ec54c14e730c30bea821c34dc4c48;hp=415c1e89835d7eeb51f1da8d9d18e330da60ad64;hpb=d77f8181b434e3213611927e9e818d930121a5d1;p=oota-llvm.git diff --git a/lib/Target/X86/SSEDomainFix.cpp b/lib/Target/X86/SSEDomainFix.cpp index 415c1e89835..13680c592e0 100644 --- a/lib/Target/X86/SSEDomainFix.cpp +++ b/lib/Target/X86/SSEDomainFix.cpp @@ -23,51 +23,12 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" - using namespace llvm; -namespace { - -/// Allocate objects from a pool, allow objects to be recycled, and provide a -/// way of deleting everything. -template -class PoolAllocator { - std::vector Pages, Avail; -public: - ~PoolAllocator() { Clear(); } - - T* Alloc() { - if (Avail.empty()) { - T *p = new T[PageSize]; - Pages.push_back(p); - Avail.reserve(PageSize); - for (unsigned n = 0; n != PageSize; ++n) - Avail.push_back(p+n); - } - T *p = Avail.back(); - Avail.pop_back(); - return p; - } - - // Allow object to be reallocated. It won't be reconstructed. - void Recycle(T *p) { - p->clear(); - Avail.push_back(p); - } - - // Destroy all objects, make sure there are no external pointers to them. - void Clear() { - Avail.clear(); - while (!Pages.empty()) { - delete[] Pages.back(); - Pages.pop_back(); - } - } -}; - -/// A DomainValue is a bit like LiveIntervals' ValNo, but it laso keeps track +/// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track /// of execution domains. /// /// An open DomainValue represents a set of instructions that can still switch @@ -82,14 +43,15 @@ public: /// domain, but if we were forced to pay the penalty of a domain crossing, we /// keep track of the fact the the register is now available in multiple /// domains. +namespace { struct DomainValue { // Basic reference counting. unsigned Refs; - // Available domains. For an open DomainValue, it is the still possible - // domains for collapsing. For a collapsed DomainValue it is the domains where - // the register is available for free. - unsigned Mask; + // Bitmask of available domains. For an open DomainValue, it is the still + // possible domains for collapsing. For a collapsed DomainValue it is the + // domains where the register is available for free. + unsigned AvailableDomains; // Position of the last defining instruction. unsigned Dist; @@ -97,42 +59,63 @@ struct DomainValue { // Twiddleable instructions using or defining these registers. SmallVector Instrs; - // Collapsed DomainValue have no instructions to twiddle - it simply keeps + // A collapsed DomainValue has no instructions to twiddle - it simply keeps // track of the domains where the registers are already available. - bool collapsed() const { return Instrs.empty(); } + bool isCollapsed() const { return Instrs.empty(); } + + // Is domain available? + bool hasDomain(unsigned domain) const { + return AvailableDomains & (1u << domain); + } - // Is any domain in mask available? - bool compat(unsigned mask) const { - return Mask & mask; + // Mark domain as available. + void addDomain(unsigned domain) { + AvailableDomains |= 1u << domain; } - // Mark domain as available - void add(unsigned domain) { - Mask |= 1u << domain; + // Restrict to a single domain available. + void setSingleDomain(unsigned domain) { + AvailableDomains = 1u << domain; + } + + // Return bitmask of domains that are available and in mask. + unsigned getCommonDomains(unsigned mask) const { + return AvailableDomains & mask; + } + + // First domain available. + unsigned getFirstDomain() const { + return CountTrailingZeros_32(AvailableDomains); } DomainValue() { clear(); } void clear() { - Refs = Mask = Dist = 0; + Refs = AvailableDomains = Dist = 0; Instrs.clear(); } }; +} + +static const unsigned NumRegs = 16; +namespace { class SSEDomainFixPass : public MachineFunctionPass { static char ID; - PoolAllocator Pool; + SpecificBumpPtrAllocator Allocator; + SmallVector Avail; MachineFunction *MF; const X86InstrInfo *TII; const TargetRegisterInfo *TRI; - MachineBasicBlock *MBB; - bool hasLiveRegs; - DomainValue *LiveRegs[16]; + DomainValue **LiveRegs; + typedef DenseMap LiveOutMap; + LiveOutMap LiveOuts; + unsigned Distance; public: - SSEDomainFixPass() : MachineFunctionPass(&ID) {} + SSEDomainFixPass() : MachineFunctionPass(ID) {} virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); @@ -149,6 +132,10 @@ private: // Register mapping. int RegIndex(unsigned Reg); + // DomainValue allocation. + DomainValue *Alloc(int domain = -1); + void Recycle(DomainValue*); + // LiveRegs manipulations. void SetLiveReg(int rx, DomainValue *DV); void Kill(int rx); @@ -156,11 +143,10 @@ private: void Collapse(DomainValue *dv, unsigned domain); bool Merge(DomainValue *A, DomainValue *B); - void enterBasicBlock(MachineBasicBlock *MBB); + void enterBasicBlock(); void visitGenericInstr(MachineInstr*); void visitSoftInstr(MachineInstr*, unsigned mask); void visitHardInstr(MachineInstr*, unsigned domain); - }; } @@ -169,20 +155,40 @@ char SSEDomainFixPass::ID = 0; /// Translate TRI register number to an index into our smaller tables of /// interesting registers. Return -1 for boring registers. int SSEDomainFixPass::RegIndex(unsigned reg) { - // Registers are sorted lexicographically. - // We just need them to be consecutive, ordering doesn't matter. - assert(X86::XMM9 == X86::XMM0+15 && "Unexpected sort"); + assert(X86::XMM15 == X86::XMM0+NumRegs-1 && "Unexpected sort"); reg -= X86::XMM0; - return reg < 16 ? reg : -1; + return reg < NumRegs ? (int) reg : -1; +} + +DomainValue *SSEDomainFixPass::Alloc(int domain) { + DomainValue *dv = Avail.empty() ? + new(Allocator.Allocate()) DomainValue : + Avail.pop_back_val(); + dv->Dist = Distance; + if (domain >= 0) + dv->addDomain(domain); + return dv; +} + +void SSEDomainFixPass::Recycle(DomainValue *dv) { + assert(dv && "Cannot recycle NULL"); + dv->clear(); + Avail.push_back(dv); } /// Set LiveRegs[rx] = dv, updating reference counts. void SSEDomainFixPass::SetLiveReg(int rx, DomainValue *dv) { + assert(unsigned(rx) < NumRegs && "Invalid index"); + if (!LiveRegs) { + LiveRegs = new DomainValue*[NumRegs]; + std::fill(LiveRegs, LiveRegs+NumRegs, (DomainValue*)0); + } + if (LiveRegs[rx] == dv) return; if (LiveRegs[rx]) { assert(LiveRegs[rx]->Refs && "Bad refcount"); - if (--LiveRegs[rx]->Refs == 0) Pool.Recycle(LiveRegs[rx]); + if (--LiveRegs[rx]->Refs == 0) Recycle(LiveRegs[rx]); } LiveRegs[rx] = dv; if (dv) ++dv->Refs; @@ -190,76 +196,109 @@ void SSEDomainFixPass::SetLiveReg(int rx, DomainValue *dv) { // Kill register rx, recycle or collapse any DomainValue. void SSEDomainFixPass::Kill(int rx) { - if (!LiveRegs[rx]) return; + assert(unsigned(rx) < NumRegs && "Invalid index"); + if (!LiveRegs || !LiveRegs[rx]) return; // Before killing the last reference to an open DomainValue, collapse it to // the first available domain. - if (LiveRegs[rx]->Refs == 1 && !LiveRegs[rx]->collapsed()) - Collapse(LiveRegs[rx], CountTrailingZeros_32(LiveRegs[rx]->Mask)); + if (LiveRegs[rx]->Refs == 1 && !LiveRegs[rx]->isCollapsed()) + Collapse(LiveRegs[rx], LiveRegs[rx]->getFirstDomain()); else SetLiveReg(rx, 0); } /// Force register rx into domain. void SSEDomainFixPass::Force(int rx, unsigned domain) { - hasLiveRegs = true; + assert(unsigned(rx) < NumRegs && "Invalid index"); DomainValue *dv; - if ((dv = LiveRegs[rx])) { - if (dv->collapsed()) - dv->add(domain); - else + if (LiveRegs && (dv = LiveRegs[rx])) { + if (dv->isCollapsed()) + dv->addDomain(domain); + else if (dv->hasDomain(domain)) Collapse(dv, domain); + else { + // This is an incompatible open DomainValue. Collapse it to whatever and force + // the new value into domain. This costs a domain crossing. + Collapse(dv, dv->getFirstDomain()); + assert(LiveRegs[rx] && "Not live after collapse?"); + LiveRegs[rx]->addDomain(domain); + } } else { - // Set up basic collapsed DomainValue - dv = Pool.Alloc(); - dv->add(domain); - SetLiveReg(rx, dv); + // Set up basic collapsed DomainValue. + SetLiveReg(rx, Alloc(domain)); } } /// Collapse open DomainValue into given domain. If there are multiple /// registers using dv, they each get a unique collapsed DomainValue. void SSEDomainFixPass::Collapse(DomainValue *dv, unsigned domain) { - assert(dv->compat(1u << domain) && "Cannot collapse"); + assert(dv->hasDomain(domain) && "Cannot collapse"); // Collapse all the instructions. - while (!dv->Instrs.empty()) { - MachineInstr *mi = dv->Instrs.back(); - TII->SetSSEDomain(mi, domain); - dv->Instrs.pop_back(); - } - dv->Mask = 1u << domain; + while (!dv->Instrs.empty()) + TII->SetSSEDomain(dv->Instrs.pop_back_val(), domain); + dv->setSingleDomain(domain); // If there are multiple users, give them new, unique DomainValues. - if (dv->Refs > 1) { - for (unsigned rx=0, e = array_lengthof(LiveRegs); rx != e; ++rx) - if (LiveRegs[rx] == dv) { - DomainValue *dv2 = Pool.Alloc(); - dv2->add(domain); - SetLiveReg(rx, dv2); - } - Pool.Recycle(dv); - } + if (LiveRegs && dv->Refs > 1) + for (unsigned rx = 0; rx != NumRegs; ++rx) + if (LiveRegs[rx] == dv) + SetLiveReg(rx, Alloc(domain)); } /// Merge - All instructions and registers in B are moved to A, and B is /// released. bool SSEDomainFixPass::Merge(DomainValue *A, DomainValue *B) { - assert(!A->collapsed() && "Cannot merge into collapsed"); - assert(!B->collapsed() && "Cannot merge from collapsed"); - if (!A->compat(B->Mask)) + assert(!A->isCollapsed() && "Cannot merge into collapsed"); + assert(!B->isCollapsed() && "Cannot merge from collapsed"); + if (A == B) + return true; + // Restrict to the domains that A and B have in common. + unsigned common = A->getCommonDomains(B->AvailableDomains); + if (!common) return false; - A->Mask &= B->Mask; + A->AvailableDomains = common; A->Dist = std::max(A->Dist, B->Dist); A->Instrs.append(B->Instrs.begin(), B->Instrs.end()); - for (unsigned rx=0, e = array_lengthof(LiveRegs); rx != e; ++rx) + for (unsigned rx = 0; rx != NumRegs; ++rx) if (LiveRegs[rx] == B) SetLiveReg(rx, A); return true; } -void SSEDomainFixPass::enterBasicBlock(MachineBasicBlock *mbb) { - MBB = mbb; +void SSEDomainFixPass::enterBasicBlock() { + // Try to coalesce live-out registers from predecessors. + for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(), + e = MBB->livein_end(); i != e; ++i) { + int rx = RegIndex(*i); + if (rx < 0) continue; + for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(), + pe = MBB->pred_end(); pi != pe; ++pi) { + LiveOutMap::const_iterator fi = LiveOuts.find(*pi); + if (fi == LiveOuts.end()) continue; + DomainValue *pdv = fi->second[rx]; + if (!pdv) continue; + if (!LiveRegs || !LiveRegs[rx]) { + SetLiveReg(rx, pdv); + continue; + } + + // We have a live DomainValue from more than one predecessor. + if (LiveRegs[rx]->isCollapsed()) { + // We are already collapsed, but predecessor is not. Force him. + unsigned domain = LiveRegs[rx]->getFirstDomain(); + if (!pdv->isCollapsed() && pdv->hasDomain(domain)) + Collapse(pdv, domain); + continue; + } + + // Currently open, merge in predecessor. + if (!pdv->isCollapsed()) + Merge(LiveRegs[rx], pdv); + else + Force(rx, pdv->getFirstDomain()); + } + } } // A hard instruction only works in one domain. All input registers will be @@ -288,43 +327,54 @@ void SSEDomainFixPass::visitHardInstr(MachineInstr *mi, unsigned domain) { // A soft instruction can be changed to work in other domains given by mask. void SSEDomainFixPass::visitSoftInstr(MachineInstr *mi, unsigned mask) { + // Bitmask of available domains for this instruction after taking collapsed + // operands into account. + unsigned available = mask; + // Scan the explicit use operands for incoming domains. - unsigned collmask = mask; SmallVector used; - for (unsigned i = mi->getDesc().getNumDefs(), - e = mi->getDesc().getNumOperands(); i != e; ++i) { - MachineOperand &mo = mi->getOperand(i); - if (!mo.isReg()) continue; - int rx = RegIndex(mo.getReg()); - if (rx < 0) continue; - if (DomainValue *dv = LiveRegs[rx]) { - // Is it possible to use this collapsed register for free? - if (dv->collapsed()) { - if (unsigned m = collmask & dv->Mask) - collmask = m; - } else if (dv->compat(collmask)) - used.push_back(rx); - else - Kill(rx); + if (LiveRegs) + for (unsigned i = mi->getDesc().getNumDefs(), + e = mi->getDesc().getNumOperands(); i != e; ++i) { + MachineOperand &mo = mi->getOperand(i); + if (!mo.isReg()) continue; + int rx = RegIndex(mo.getReg()); + if (rx < 0) continue; + if (DomainValue *dv = LiveRegs[rx]) { + // Bitmask of domains that dv and available have in common. + unsigned common = dv->getCommonDomains(available); + // 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 + // penalty for this operand. + if (common) available = common; + } else if (common) + // Open DomainValue is compatible, save it for merging. + used.push_back(rx); + else + // Open DomainValue is not compatible with instruction. It is useless + // now. + Kill(rx); + } } - } // If the collapsed operands force a single domain, propagate the collapse. - if (isPowerOf2_32(collmask)) { - unsigned domain = CountTrailingZeros_32(collmask); + if (isPowerOf2_32(available)) { + unsigned domain = CountTrailingZeros_32(available); TII->SetSSEDomain(mi, domain); visitHardInstr(mi, domain); return; } - // Kill off any remaining uses that don't match collmask, and build a list of - // incoming DomainValue that we want to merge. + // Kill off any remaining uses that don't match available, and build a list of + // incoming DomainValues that we want to merge. SmallVector doms; for (SmallVector::iterator i=used.begin(), e=used.end(); i!=e; ++i) { int rx = *i; DomainValue *dv = LiveRegs[rx]; - // This useless DomainValue could have been missed above - if (!dv->compat(collmask)) { + // This useless DomainValue could have been missed above. + if (!dv->getCommonDomains(available)) { Kill(*i); continue; } @@ -343,23 +393,29 @@ void SSEDomainFixPass::visitSoftInstr(MachineInstr *mi, unsigned mask) { doms.push_back(dv); } - // doms are now sorted in order of appearance. Try to merge them all, giving - // priority to the latest ones. + // doms are now sorted in order of appearance. Try to merge them all, giving + // priority to the latest ones. DomainValue *dv = 0; while (!doms.empty()) { - if (!dv) - dv = doms.back(); - else if (!Merge(dv, doms.back())) - for (SmallVector::iterator i=used.begin(), e=used.end(); i!=e; ++i) - if (LiveRegs[*i] == doms.back()) - Kill(*i); - doms.pop_back(); + if (!dv) { + dv = doms.pop_back_val(); + continue; + } + + DomainValue *latest = doms.pop_back_val(); + if (Merge(dv, latest)) 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) + if (LiveRegs[*i] == latest) + Kill(*i); } // dv is the DomainValue we are going to use for this instruction. if (!dv) - dv = Pool.Alloc(); - dv->Mask = collmask; + dv = Alloc(); + dv->Dist = Distance; + dv->AvailableDomains = available; dv->Instrs.push_back(mi); // Finally set all defs and non-collapsed uses to dv. @@ -368,7 +424,7 @@ void SSEDomainFixPass::visitSoftInstr(MachineInstr *mi, unsigned mask) { if (!mo.isReg()) continue; int rx = RegIndex(mo.getReg()); if (rx < 0) continue; - if (!LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) { + if (!LiveRegs || !LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) { Kill(rx); SetLiveReg(rx, dv); } @@ -376,7 +432,7 @@ void SSEDomainFixPass::visitSoftInstr(MachineInstr *mi, unsigned mask) { } void SSEDomainFixPass::visitGenericInstr(MachineInstr *mi) { - // Process explicit defs, kill any XMM registers redefined + // Process explicit defs, kill any XMM registers redefined. for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) { MachineOperand &mo = mi->getOperand(i); if (!mo.isReg()) continue; @@ -391,10 +447,9 @@ bool SSEDomainFixPass::runOnMachineFunction(MachineFunction &mf) { TII = static_cast(MF->getTarget().getInstrInfo()); TRI = MF->getTarget().getRegisterInfo(); MBB = 0; - - hasLiveRegs = false; - for (unsigned i=0, e = array_lengthof(LiveRegs); i != e; ++i) - LiveRegs[i] = 0; + LiveRegs = 0; + Distance = 0; + assert(NumRegs == X86::VR128RegClass.getNumRegs() && "Bad regclass"); // If no XMM registers are used in the function, we can skip it completely. bool anyregs = false; @@ -411,23 +466,37 @@ bool SSEDomainFixPass::runOnMachineFunction(MachineFunction &mf) { for (df_ext_iterator > DFI = df_ext_begin(Entry, Visited), DFE = df_ext_end(Entry, Visited); DFI != DFE; ++DFI) { - enterBasicBlock(*DFI); + MBB = *DFI; + enterBasicBlock(); for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { MachineInstr *mi = I; if (mi->isDebugValue()) continue; + ++Distance; std::pair domp = TII->GetSSEDomain(mi); if (domp.first) if (domp.second) visitSoftInstr(mi, domp.second); else visitHardInstr(mi, domp.first); - else if (hasLiveRegs) + else if (LiveRegs) visitGenericInstr(mi); } + + // Save live registers at end of MBB - used by enterBasicBlock(). + if (LiveRegs) + LiveOuts.insert(std::make_pair(MBB, LiveRegs)); + LiveRegs = 0; } - Pool.Clear(); + // Clear the LiveOuts vectors. Should we also collapse any remaining + // DomainValues? + for (LiveOutMap::const_iterator i = LiveOuts.begin(), e = LiveOuts.end(); + i != e; ++i) + delete[] i->second; + LiveOuts.clear(); + Avail.clear(); + Allocator.DestroyAll(); return false; }