#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
// Position of the last defining instruction.
unsigned Dist;
+ // 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.
+ DomainValue *Next;
+
// Twiddleable instructions using or defining these registers.
SmallVector<MachineInstr*, 8> Instrs;
return CountTrailingZeros_32(AvailableDomains);
}
- DomainValue() { clear(); }
+ DomainValue() : Refs(0) { clear(); }
+ // Clear this DomainValue and point to next which has all its data.
void clear() {
- Refs = AvailableDomains = Dist = 0;
+ AvailableDomains = Dist = 0;
+ Next = 0;
Instrs.clear();
}
};
private:
// Register mapping.
- int RegIndex(unsigned Reg);
+ int regIndex(unsigned Reg);
// DomainValue allocation.
- DomainValue *Alloc(int domain = -1);
- void Recycle(DomainValue*);
+ DomainValue *alloc(int domain = -1);
+ DomainValue *retain(DomainValue *DV) {
+ if (DV) ++DV->Refs;
+ return DV;
+ }
+ void release(DomainValue*);
+ DomainValue *resolve(DomainValue*&);
// LiveRegs manipulations.
- void SetLiveReg(int rx, DomainValue *DV);
- void Kill(int rx);
- void Force(int rx, unsigned domain);
- void Collapse(DomainValue *dv, unsigned domain);
- bool Merge(DomainValue *A, DomainValue *B);
+ void setLiveReg(int rx, DomainValue *DV);
+ void kill(int rx);
+ void force(int rx, unsigned domain);
+ void collapse(DomainValue *dv, unsigned domain);
+ bool merge(DomainValue *A, DomainValue *B);
- void enterBasicBlock(MachineBasicBlock*);
+ bool enterBasicBlock(MachineBasicBlock*);
void leaveBasicBlock(MachineBasicBlock*);
void visitInstr(MachineInstr*);
void visitGenericInstr(MachineInstr*);
/// Translate TRI register number to an index into our smaller tables of
/// interesting registers. Return -1 for boring registers.
-int ExeDepsFix::RegIndex(unsigned Reg) {
+int ExeDepsFix::regIndex(unsigned Reg) {
assert(Reg < AliasMap.size() && "Invalid register");
return AliasMap[Reg];
}
-DomainValue *ExeDepsFix::Alloc(int domain) {
+DomainValue *ExeDepsFix::alloc(int domain) {
DomainValue *dv = Avail.empty() ?
new(Allocator.Allocate()) DomainValue :
Avail.pop_back_val();
dv->Dist = Distance;
if (domain >= 0)
dv->addDomain(domain);
+ assert(dv->Refs == 0 && "Reference count wasn't cleared");
+ assert(!dv->Next && "Chained DomainValue shouldn't have been recycled");
return dv;
}
-void ExeDepsFix::Recycle(DomainValue *dv) {
- assert(dv && "Cannot recycle NULL");
- dv->clear();
- Avail.push_back(dv);
+/// release - Release a reference to DV. When the last reference is released,
+/// collapse if needed.
+void ExeDepsFix::release(DomainValue *DV) {
+ while (DV) {
+ assert(DV->Refs && "Bad DomainValue");
+ if (--DV->Refs)
+ return;
+
+ // There are no more DV references. Collapse any contained instructions.
+ if (DV->AvailableDomains && !DV->isCollapsed())
+ collapse(DV, DV->getFirstDomain());
+
+ DomainValue *Next = DV->Next;
+ DV->clear();
+ Avail.push_back(DV);
+ // Also release the next DomainValue in the chain.
+ DV = Next;
+ }
+}
+
+/// resolve - Follow the chain of dead DomainValues until a live DomainValue is
+/// reached. Update the referenced pointer when necessary.
+DomainValue *ExeDepsFix::resolve(DomainValue *&DVRef) {
+ DomainValue *DV = DVRef;
+ if (!DV || !DV->Next)
+ return DV;
+
+ // DV has a chain. Find the end.
+ do DV = DV->Next;
+ while (DV->Next);
+
+ // Update DVRef to point to DV.
+ retain(DV);
+ release(DVRef);
+ DVRef = DV;
+ return DV;
}
/// Set LiveRegs[rx] = dv, updating reference counts.
-void ExeDepsFix::SetLiveReg(int rx, DomainValue *dv) {
+void ExeDepsFix::setLiveReg(int rx, DomainValue *dv) {
assert(unsigned(rx) < NumRegs && "Invalid index");
if (!LiveRegs) {
LiveRegs = new DomainValue*[NumRegs];
if (LiveRegs[rx] == dv)
return;
- if (LiveRegs[rx]) {
- assert(LiveRegs[rx]->Refs && "Bad refcount");
- if (--LiveRegs[rx]->Refs == 0) Recycle(LiveRegs[rx]);
- }
- LiveRegs[rx] = dv;
- if (dv) ++dv->Refs;
+ if (LiveRegs[rx])
+ release(LiveRegs[rx]);
+ LiveRegs[rx] = retain(dv);
}
// Kill register rx, recycle or collapse any DomainValue.
-void ExeDepsFix::Kill(int rx) {
+void ExeDepsFix::kill(int rx) {
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]->isCollapsed())
- Collapse(LiveRegs[rx], LiveRegs[rx]->getFirstDomain());
- else
- SetLiveReg(rx, 0);
+ release(LiveRegs[rx]);
+ LiveRegs[rx] = 0;
}
/// Force register rx into domain.
-void ExeDepsFix::Force(int rx, unsigned domain) {
+void ExeDepsFix::force(int rx, unsigned domain) {
assert(unsigned(rx) < NumRegs && "Invalid index");
DomainValue *dv;
if (LiveRegs && (dv = LiveRegs[rx])) {
if (dv->isCollapsed())
dv->addDomain(domain);
else if (dv->hasDomain(domain))
- Collapse(dv, 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());
+ collapse(dv, dv->getFirstDomain());
assert(LiveRegs[rx] && "Not live after collapse?");
LiveRegs[rx]->addDomain(domain);
}
} else {
// Set up basic collapsed DomainValue.
- SetLiveReg(rx, Alloc(domain));
+ 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 ExeDepsFix::Collapse(DomainValue *dv, unsigned domain) {
+void ExeDepsFix::collapse(DomainValue *dv, unsigned domain) {
assert(dv->hasDomain(domain) && "Cannot collapse");
// Collapse all the instructions.
if (LiveRegs && dv->Refs > 1)
for (unsigned rx = 0; rx != NumRegs; ++rx)
if (LiveRegs[rx] == dv)
- SetLiveReg(rx, Alloc(domain));
+ setLiveReg(rx, alloc(domain));
}
/// Merge - All instructions and registers in B are moved to A, and B is
/// released.
-bool ExeDepsFix::Merge(DomainValue *A, DomainValue *B) {
+bool ExeDepsFix::merge(DomainValue *A, DomainValue *B) {
assert(!A->isCollapsed() && "Cannot merge into collapsed");
assert(!B->isCollapsed() && "Cannot merge from collapsed");
if (A == B)
A->AvailableDomains = common;
A->Dist = std::max(A->Dist, B->Dist);
A->Instrs.append(B->Instrs.begin(), B->Instrs.end());
+
+ // Clear the old DomainValue so we won't try to swizzle instructions twice.
+ B->clear();
+ // All uses of B are referred to A.
+ B->Next = retain(A);
+
for (unsigned rx = 0; rx != NumRegs; ++rx)
if (LiveRegs[rx] == B)
- SetLiveReg(rx, A);
+ setLiveReg(rx, A);
return true;
}
-void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
+// enterBasicBlock - Set up LiveRegs by merging predecessor live-out values.
+// Return true if some predecessor hasn't been processed yet (like on a loop
+// back-edge).
+bool ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) {
+ // Detect back-edges from predecessors we haven't processed yet.
+ bool seenBackEdge = false;
+
// 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);
+ 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 (fi == LiveOuts.end()) {
+ seenBackEdge = true;
+ continue;
+ }
+ if (!fi->second)
+ continue;
+ DomainValue *pdv = resolve(fi->second[rx]);
if (!pdv) continue;
if (!LiveRegs || !LiveRegs[rx]) {
- SetLiveReg(rx, pdv);
+ setLiveReg(rx, pdv);
continue;
}
// We are already collapsed, but predecessor is not. Force him.
unsigned domain = LiveRegs[rx]->getFirstDomain();
if (!pdv->isCollapsed() && pdv->hasDomain(domain))
- Collapse(pdv, domain);
+ collapse(pdv, domain);
continue;
}
// Currently open, merge in predecessor.
if (!pdv->isCollapsed())
- Merge(LiveRegs[rx], pdv);
+ merge(LiveRegs[rx], pdv);
else
- Force(rx, pdv->getFirstDomain());
+ force(rx, pdv->getFirstDomain());
}
}
+ return seenBackEdge;
}
void ExeDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) {
// Save live registers at end of MBB - used by enterBasicBlock().
- if (LiveRegs)
- LiveOuts.insert(std::make_pair(MBB, LiveRegs));
+ // Also use LiveOuts as a visited set to detect back-edges.
+ if (!LiveOuts.insert(std::make_pair(MBB, LiveRegs)).second && LiveRegs) {
+ // Insertion failed, this must be the second pass.
+ // Release all the DomainValues instead of keeping them.
+ for (unsigned i = 0, e = NumRegs; i != e; ++i)
+ release(LiveRegs[i]);
+ delete[] LiveRegs;
+ }
LiveRegs = 0;
}
e = mi->getDesc().getNumOperands(); i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg()) continue;
- int rx = RegIndex(mo.getReg());
+ int rx = regIndex(mo.getReg());
if (rx < 0) continue;
- Force(rx, domain);
+ force(rx, domain);
}
// Kill all defs and force them.
for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg()) continue;
- int rx = RegIndex(mo.getReg());
+ int rx = regIndex(mo.getReg());
if (rx < 0) continue;
- Kill(rx);
- Force(rx, domain);
+ kill(rx);
+ force(rx, domain);
}
}
e = mi->getDesc().getNumOperands(); i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg()) continue;
- int rx = RegIndex(mo.getReg());
+ int rx = regIndex(mo.getReg());
if (rx < 0) continue;
if (DomainValue *dv = LiveRegs[rx]) {
// Bitmask of domains that dv and available have in common.
else
// Open DomainValue is not compatible with instruction. It is useless
// now.
- Kill(rx);
+ kill(rx);
}
}
DomainValue *dv = LiveRegs[rx];
// This useless DomainValue could have been missed above.
if (!dv->getCommonDomains(available)) {
- Kill(*i);
+ kill(*i);
continue;
}
// sorted, uniqued insert.
}
DomainValue *latest = doms.pop_back_val();
- if (Merge(dv, latest)) continue;
+ if (merge(dv, latest)) continue;
// If latest didn't merge, it is useless now. Kill all registers using it.
for (SmallVector<int,4>::iterator i=used.begin(), e=used.end(); i != e; ++i)
if (LiveRegs[*i] == latest)
- Kill(*i);
+ kill(*i);
}
// dv is the DomainValue we are going to use for this instruction.
if (!dv)
- dv = Alloc();
+ dv = alloc();
dv->Dist = Distance;
dv->AvailableDomains = available;
dv->Instrs.push_back(mi);
for (unsigned i = 0, e = mi->getDesc().getNumOperands(); i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg()) continue;
- int rx = RegIndex(mo.getReg());
+ int rx = regIndex(mo.getReg());
if (rx < 0) continue;
if (!LiveRegs || !LiveRegs[rx] || (mo.isDef() && LiveRegs[rx]!=dv)) {
- Kill(rx);
- SetLiveReg(rx, dv);
+ kill(rx);
+ setLiveReg(rx, dv);
}
}
}
for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) {
MachineOperand &mo = mi->getOperand(i);
if (!mo.isReg()) continue;
- int rx = RegIndex(mo.getReg());
+ int rx = regIndex(mo.getReg());
if (rx < 0) continue;
- Kill(rx);
+ kill(rx);
}
}
}
MachineBasicBlock *Entry = MF->begin();
- SmallPtrSet<MachineBasicBlock*, 16> Visited;
- for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*, 16> >
- DFI = df_ext_begin(Entry, Visited), DFE = df_ext_end(Entry, Visited);
- DFI != DFE; ++DFI) {
- MachineBasicBlock *MBB = *DFI;
- enterBasicBlock(MBB);
+ ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry);
+ SmallVector<MachineBasicBlock*, 16> Loops;
+ for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
+ MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
+ MachineBasicBlock *MBB = *MBBI;
+ if (enterBasicBlock(MBB))
+ Loops.push_back(MBB);
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
++I)
visitInstr(I);
leaveBasicBlock(MBB);
}
- // 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;
+ // Visit all the loop blocks again in order to merge DomainValues from
+ // back-edges.
+ for (unsigned i = 0, e = Loops.size(); i != e; ++i) {
+ MachineBasicBlock *MBB = Loops[i];
+ enterBasicBlock(MBB);
+ leaveBasicBlock(MBB);
+ }
+
+ // Clear the LiveOuts vectors and collapse any remaining DomainValues.
+ for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator
+ MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) {
+ LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI);
+ if (FI == LiveOuts.end() || !FI->second)
+ continue;
+ for (unsigned i = 0, e = NumRegs; i != e; ++i)
+ if (FI->second[i])
+ release(FI->second[i]);
+ delete[] FI->second;
+ }
LiveOuts.clear();
Avail.clear();
Allocator.DestroyAll();
projects / oota-llvm.git / blobdiff