X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTarget%2FX86%2FSSEDomainFix.cpp;h=13680c592e01b274dbfca95729fa68147ba43598;hb=c146c4d47a7ec54c14e730c30bea821c34dc4c48;hp=be17515184a3733a98b8e28e70342272560ec967;hpb=5f282b5dfdfcc6afe2eb27d7d04766f9f33cb1f4;p=oota-llvm.git diff --git a/lib/Target/X86/SSEDomainFix.cpp b/lib/Target/X86/SSEDomainFix.cpp index be17515184a..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,38 +59,51 @@ 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 any domain in mask available? - bool compat(unsigned mask) const { - return Mask & mask; + // Is domain available? + bool hasDomain(unsigned domain) const { + return AvailableDomains & (1u << domain); } // Mark domain as available. - void add(unsigned domain) { - Mask |= 1u << domain; + void addDomain(unsigned domain) { + AvailableDomains |= 1u << domain; + } + + // Restrict to a single domain available. + void setSingleDomain(unsigned domain) { + AvailableDomains = 1u << domain; } - // First domain available in mask. - unsigned firstDomain() const { - return CountTrailingZeros_32(Mask); + // 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; @@ -140,7 +115,7 @@ class SSEDomainFixPass : public MachineFunctionPass { unsigned Distance; public: - SSEDomainFixPass() : MachineFunctionPass(&ID) {} + SSEDomainFixPass() : MachineFunctionPass(ID) {} virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); @@ -157,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); @@ -168,7 +147,6 @@ private: void visitGenericInstr(MachineInstr*); void visitSoftInstr(MachineInstr*, unsigned mask); void visitHardInstr(MachineInstr*, unsigned domain); - }; } @@ -177,24 +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+NumRegs-1 && "Unexpected sort"); + assert(X86::XMM15 == X86::XMM0+NumRegs-1 && "Unexpected sort"); reg -= X86::XMM0; - return reg < NumRegs ? 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 = (DomainValue**)calloc(sizeof(DomainValue*), NumRegs); + 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; @@ -207,8 +201,8 @@ void SSEDomainFixPass::Kill(int rx) { // 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], LiveRegs[rx]->firstDomain()); + if (LiveRegs[rx]->Refs == 1 && !LiveRegs[rx]->isCollapsed()) + Collapse(LiveRegs[rx], LiveRegs[rx]->getFirstDomain()); else SetLiveReg(rx, 0); } @@ -218,54 +212,52 @@ void SSEDomainFixPass::Force(int rx, unsigned domain) { assert(unsigned(rx) < NumRegs && "Invalid index"); DomainValue *dv; if (LiveRegs && (dv = LiveRegs[rx])) { - if (dv->collapsed()) - dv->add(domain); - else + 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->Dist = Distance; - dv->add(domain); - SetLiveReg(rx, dv); + 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 (LiveRegs && dv->Refs > 1) { + if (LiveRegs && dv->Refs > 1) for (unsigned rx = 0; rx != NumRegs; ++rx) - if (LiveRegs[rx] == dv) { - DomainValue *dv2 = Pool.Alloc(); - dv2->Dist = Distance; - dv2->add(domain); - SetLiveReg(rx, dv2); - } - } + 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 == B) + assert(!A->isCollapsed() && "Cannot merge into collapsed"); + assert(!B->isCollapsed() && "Cannot merge from collapsed"); + if (A == B) return true; - if (!A->compat(B->Mask)) + // 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; rx != NumRegs; ++rx) @@ -276,7 +268,7 @@ bool SSEDomainFixPass::Merge(DomainValue *A, DomainValue *B) { void SSEDomainFixPass::enterBasicBlock() { // Try to coalesce live-out registers from predecessors. - for (MachineBasicBlock::const_livein_iterator i = MBB->livein_begin(), + for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(), e = MBB->livein_end(); i != e; ++i) { int rx = RegIndex(*i); if (rx < 0) continue; @@ -286,22 +278,25 @@ void SSEDomainFixPass::enterBasicBlock() { if (fi == LiveOuts.end()) continue; DomainValue *pdv = fi->second[rx]; if (!pdv) continue; - if (!LiveRegs || !LiveRegs[rx]) + if (!LiveRegs || !LiveRegs[rx]) { SetLiveReg(rx, pdv); - else { - // We have a live DomainValue from more than one predecessor. - if (LiveRegs[rx]->collapsed()) { - // We are already collapsed, but predecessor is not. Force him. - if (!pdv->collapsed()) - Collapse(pdv, LiveRegs[rx]->firstDomain()); - } else { - // Currently open, merge in predecessor. - if (!pdv->collapsed()) - Merge(LiveRegs[rx], pdv); - else - Collapse(LiveRegs[rx], pdv->firstDomain()); - } + 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()); } } } @@ -332,44 +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; 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]) { - // 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); + 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)) { + if (!dv->getCommonDomains(available)) { Kill(*i); continue; } @@ -388,24 +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 = Alloc(); dv->Dist = Distance; - dv->Mask = collmask; + dv->AvailableDomains = available; dv->Instrs.push_back(mi); // Finally set all defs and non-collapsed uses to dv. @@ -483,9 +493,10 @@ bool SSEDomainFixPass::runOnMachineFunction(MachineFunction &mf) { // DomainValues? for (LiveOutMap::const_iterator i = LiveOuts.begin(), e = LiveOuts.end(); i != e; ++i) - free(i->second); + delete[] i->second; LiveOuts.clear(); - Pool.Clear(); + Avail.clear(); + Allocator.DestroyAll(); return false; }