STATISTIC(numExtends , "Number of copies extended");
STATISTIC(NumReMats , "Number of instructions re-materialized");
STATISTIC(NumInflated , "Number of register classes inflated");
+STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested");
+STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved");
static cl::opt<bool>
EnableJoining("join-liveintervals",
cl::desc("Coalesce copies (default=true)"),
cl::init(true));
+// Temporary flag to test critical edge unsplitting.
+static cl::opt<bool>
+EnableJoinSplits("join-splitedges",
+ cl::desc("Coalesce copies on split edges (default=false)"),
+ cl::init(false), cl::Hidden);
+
static cl::opt<bool>
VerifyCoalescing("verify-coalescing",
cl::desc("Verify machine instrs before and after register coalescing"),
cl::Hidden);
-// Temporary option for testing new coalescer algo.
-static cl::opt<bool>
-NewCoalescer("new-coalescer", cl::Hidden,
- cl::desc("Use new coalescer algorithm"));
-
namespace {
class RegisterCoalescer : public MachineFunctionPass,
private LiveRangeEdit::Delegate {
char RegisterCoalescer::ID = 0;
-static unsigned compose(const TargetRegisterInfo &tri, unsigned a, unsigned b) {
- if (!a) return b;
- if (!b) return a;
- return tri.composeSubRegIndices(a, b);
-}
-
static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI,
unsigned &Src, unsigned &Dst,
unsigned &SrcSub, unsigned &DstSub) {
SrcSub = MI->getOperand(1).getSubReg();
} else if (MI->isSubregToReg()) {
Dst = MI->getOperand(0).getReg();
- DstSub = compose(tri, MI->getOperand(0).getSubReg(),
- MI->getOperand(3).getImm());
+ DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),
+ MI->getOperand(3).getImm());
Src = MI->getOperand(2).getReg();
SrcSub = MI->getOperand(2).getSubReg();
} else
return true;
}
+// Return true if this block should be vacated by the coalescer to eliminate
+// branches. The important cases to handle in the coalescer are critical edges
+// split during phi elimination which contain only copies. Simple blocks that
+// contain non-branches should also be vacated, but this can be handled by an
+// earlier pass similar to early if-conversion.
+static bool isSplitEdge(const MachineBasicBlock *MBB) {
+ if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
+ return false;
+
+ for (MachineBasicBlock::const_iterator MII = MBB->begin(), E = MBB->end();
+ MII != E; ++MII) {
+ if (!MII->isCopyLike() || !MII->isUnconditionalBranch())
+ return false;
+ }
+ return true;
+}
+
bool CoalescerPair::setRegisters(const MachineInstr *MI) {
SrcReg = DstReg = 0;
SrcIdx = DstIdx = 0;
if (DstReg != Dst)
return false;
// Registers match, do the subregisters line up?
- return compose(TRI, SrcIdx, SrcSub) == compose(TRI, DstIdx, DstSub);
+ return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
+ TRI.composeSubRegIndices(DstIdx, DstSub);
}
}
// If AValNo is defined as a copy from IntB, we can potentially process this.
// Get the instruction that defines this value number.
MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def);
- if (!CP.isCoalescable(ACopyMI))
+ // Don't allow any partial copies, even if isCoalescable() allows them.
+ if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())
return false;
// Get the LiveRange in IntB that this value number starts with.
/// Always join simple intervals that are defined by a single copy from a
/// reserved register. This doesn't increase register pressure, so it is
/// always beneficial.
- if (!RegClassInfo.isReserved(CP.getDstReg())) {
+ if (!MRI->isReserved(CP.getDstReg())) {
DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
return false;
}
/// Attempt joining with a reserved physreg.
bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
assert(CP.isPhys() && "Must be a physreg copy");
- assert(RegClassInfo.isReserved(CP.getDstReg()) && "Not a reserved register");
+ assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register");
LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS
<< '\n');
// Value in the other live range that overlaps this def, if any.
VNInfo *OtherVNI;
+ // Is this value an IMPLICIT_DEF?
+ bool IsImplicitDef;
+
+ // True when the live range of this value will be pruned because of an
+ // overlapping CR_Replace value in the other live range.
+ bool Pruned;
+
+ // True once Pruned above has been computed.
+ bool PrunedComputed;
+
Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0),
- RedefVNI(0), OtherVNI(0) {}
+ RedefVNI(0), OtherVNI(0), IsImplicitDef(false), Pruned(false),
+ PrunedComputed(false) {}
bool isAnalyzed() const { return WriteLanes != 0; }
};
VNInfo *stripCopies(VNInfo *VNI);
ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
void computeAssignment(unsigned ValNo, JoinVals &Other);
+ bool taintExtent(unsigned, unsigned, JoinVals&,
+ SmallVectorImpl<std::pair<SlotIndex, unsigned> >&);
+ bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned);
+ bool isPrunedValue(unsigned ValNo, JoinVals &Other);
public:
JoinVals(LiveInterval &li, unsigned subIdx,
SmallVectorImpl<unsigned> &ShrinkRegs);
/// Get the value assignments suitable for passing to LiveInterval::join.
- const int *getAssignments() const { return &Assignments[0]; }
+ const int *getAssignments() const { return Assignments.data(); }
};
} // end anonymous namespace
for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) {
if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef())
continue;
- L |= TRI->getSubRegIndexLaneMask(compose(*TRI, SubIdx, MO->getSubReg()));
+ L |= TRI->getSubRegIndexLaneMask(
+ TRI->composeSubRegIndices(SubIdx, MO->getSubReg()));
if (MO->readsReg())
Redef = true;
}
}
// An IMPLICIT_DEF writes undef values.
- if (DefMI->isImplicitDef())
+ if (DefMI->isImplicitDef()) {
+ V.IsImplicitDef = true;
V.ValidLanes &= ~V.WriteLanes;
+ }
}
// Find the value in Other that overlaps VNI->def, if any.
// values should be merged into one, but not into any preceding value.
// The first value defined or visited gets CR_Keep, the other gets CR_Merge.
if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
- DEBUG(dbgs() << "\t\tDouble def: " << VNI->def << '\n');
assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ");
// One value stays, the other is merged. Keep the earlier one, or the first
// Keep this value, check for conflicts when analyzing OtherVNI.
if (!OtherV.isAnalyzed())
return CR_Keep;
- // Both sides have been analyzed now. Do they conflict?
+ // Both sides have been analyzed now.
+ // Allow overlapping PHI values. Any real interference would show up in a
+ // predecessor, the PHI itself can't introduce any conflicts.
+ if (VNI->isPHIDef())
+ return CR_Merge;
if (V.ValidLanes & OtherV.ValidLanes)
- // Overlapping lanes can't be resolved now, maybe later.
- return CR_Unresolved;
+ // Overlapping lanes can't be resolved.
+ return CR_Impossible;
else
return CR_Merge;
}
Other.computeAssignment(V.OtherVNI->id, *this);
const Val &OtherV = Other.Vals[V.OtherVNI->id];
- // Don't attempt resolving PHI values for now.
+ // Allow overlapping PHI values. Any real interference would show up in a
+ // predecessor, the PHI itself can't introduce any conflicts.
if (VNI->isPHIDef())
- return CR_Impossible;
+ return CR_Replace;
// Check for simple erasable conflicts.
if (DefMI->isImplicitDef())
if ((V.WriteLanes & OtherV.ValidLanes) == 0)
return CR_Replace;
- // FIXME: Identify CR_Replace opportunities where the clobbered lanes are
- // dead.
- return CR_Impossible;
+ // If the other live range is killed by DefMI and the live ranges are still
+ // overlapping, it must be because we're looking at an early clobber def:
+ //
+ // %dst<def,early-clobber> = ASM %src<kill>
+ //
+ // In this case, it is illegal to merge the two live ranges since the early
+ // clobber def would clobber %src before it was read.
+ if (OtherLRQ.isKill()) {
+ // This case where the def doesn't overlap the kill is handled above.
+ assert(VNI->def.isEarlyClobber() &&
+ "Only early clobber defs can overlap a kill");
+ return CR_Impossible;
+ }
+
+ // VNI is clobbering live lanes in OtherVNI, but there is still the
+ // possibility that no instructions actually read the clobbered lanes.
+ // If we're clobbering all the lanes in OtherVNI, at least one must be read.
+ // Otherwise Other.LI wouldn't be live here.
+ if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0)
+ return CR_Impossible;
+
+ // We need to verify that no instructions are reading the clobbered lanes. To
+ // save compile time, we'll only check that locally. Don't allow the tainted
+ // value to escape the basic block.
+ MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
+ if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
+ return CR_Impossible;
+
+ // There are still some things that could go wrong besides clobbered lanes
+ // being read, for example OtherVNI may be only partially redefined in MBB,
+ // and some clobbered lanes could escape the block. Save this analysis for
+ // resolveConflicts() when all values have been mapped. We need to know
+ // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
+ // that now - the recursive analyzeValue() calls must go upwards in the
+ // dominator tree.
+ return CR_Unresolved;
}
/// Compute the value assignment for ValNo in LI.
<< V.OtherVNI->def << " --> @"
<< NewVNInfo[Assignments[ValNo]]->def << '\n');
break;
+ case CR_Replace:
+ case CR_Unresolved:
+ // The other value is going to be pruned if this join is successful.
+ assert(V.OtherVNI && "OtherVNI not assigned, can't prune");
+ Other.Vals[V.OtherVNI->id].Pruned = true;
+ // Fall through.
default:
// This value number needs to go in the final joined live range.
Assignments[ValNo] = NewVNInfo.size();
return true;
}
+/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute
+/// the extent of the tainted lanes in the block.
+///
+/// Multiple values in Other.LI can be affected since partial redefinitions can
+/// preserve previously tainted lanes.
+///
+/// 1 %dst = VLOAD <-- Define all lanes in %dst
+/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0
+/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0
+/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
+///
+/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
+/// entry to TaintedVals.
+///
+/// Returns false if the tainted lanes extend beyond the basic block.
+bool JoinVals::
+taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other,
+ SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) {
+ VNInfo *VNI = LI.getValNumInfo(ValNo);
+ MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
+ SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
+
+ // Scan Other.LI from VNI.def to MBBEnd.
+ LiveInterval::iterator OtherI = Other.LI.find(VNI->def);
+ assert(OtherI != Other.LI.end() && "No conflict?");
+ do {
+ // OtherI is pointing to a tainted value. Abort the join if the tainted
+ // lanes escape the block.
+ SlotIndex End = OtherI->end;
+ if (End >= MBBEnd) {
+ DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':'
+ << OtherI->valno->id << '@' << OtherI->start << '\n');
+ return false;
+ }
+ DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':'
+ << OtherI->valno->id << '@' << OtherI->start
+ << " to " << End << '\n');
+ // A dead def is not a problem.
+ if (End.isDead())
+ break;
+ TaintExtent.push_back(std::make_pair(End, TaintedLanes));
+
+ // Check for another def in the MBB.
+ if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd)
+ break;
+
+ // Lanes written by the new def are no longer tainted.
+ const Val &OV = Other.Vals[OtherI->valno->id];
+ TaintedLanes &= ~OV.WriteLanes;
+ if (!OV.RedefVNI)
+ break;
+ } while (TaintedLanes);
+ return true;
+}
+
+/// Return true if MI uses any of the given Lanes from Reg.
+/// This does not include partial redefinitions of Reg.
+bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx,
+ unsigned Lanes) {
+ if (MI->isDebugValue())
+ return false;
+ for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
+ if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg)
+ continue;
+ if (!MO->readsReg())
+ continue;
+ if (Lanes & TRI->getSubRegIndexLaneMask(
+ TRI->composeSubRegIndices(SubIdx, MO->getSubReg())))
+ return true;
+ }
+ return false;
+}
+
bool JoinVals::resolveConflicts(JoinVals &Other) {
for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
- assert (Vals[i].Resolution != CR_Impossible && "Unresolvable conflict");
- if (Vals[i].Resolution != CR_Unresolved)
+ Val &V = Vals[i];
+ assert (V.Resolution != CR_Impossible && "Unresolvable conflict");
+ if (V.Resolution != CR_Unresolved)
continue;
- // FIXME: Actually resolve dead lane conflicts.
DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i
<< '@' << LI.getValNumInfo(i)->def << '\n');
- return false;
+ ++NumLaneConflicts;
+ assert(V.OtherVNI && "Inconsistent conflict resolution.");
+ VNInfo *VNI = LI.getValNumInfo(i);
+ const Val &OtherV = Other.Vals[V.OtherVNI->id];
+
+ // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
+ // join, those lanes will be tainted with a wrong value. Get the extent of
+ // the tainted lanes.
+ unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
+ SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent;
+ if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
+ // Tainted lanes would extend beyond the basic block.
+ return false;
+
+ assert(!TaintExtent.empty() && "There should be at least one conflict.");
+
+ // Now look at the instructions from VNI->def to TaintExtent (inclusive).
+ MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
+ MachineBasicBlock::iterator MI = MBB->begin();
+ if (!VNI->isPHIDef()) {
+ MI = Indexes->getInstructionFromIndex(VNI->def);
+ // No need to check the instruction defining VNI for reads.
+ ++MI;
+ }
+ assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&
+ "Interference ends on VNI->def. Should have been handled earlier");
+ MachineInstr *LastMI =
+ Indexes->getInstructionFromIndex(TaintExtent.front().first);
+ assert(LastMI && "Range must end at a proper instruction");
+ unsigned TaintNum = 0;
+ for(;;) {
+ assert(MI != MBB->end() && "Bad LastMI");
+ if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) {
+ DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);
+ return false;
+ }
+ // LastMI is the last instruction to use the current value.
+ if (&*MI == LastMI) {
+ if (++TaintNum == TaintExtent.size())
+ break;
+ LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
+ assert(LastMI && "Range must end at a proper instruction");
+ TaintedLanes = TaintExtent[TaintNum].second;
+ }
+ ++MI;
+ }
+
+ // The tainted lanes are unused.
+ V.Resolution = CR_Replace;
+ ++NumLaneResolves;
}
return true;
}
+// Determine if ValNo is a copy of a value number in LI or Other.LI that will
+// be pruned:
+//
+// %dst = COPY %src
+// %src = COPY %dst <-- This value to be pruned.
+// %dst = COPY %src <-- This value is a copy of a pruned value.
+//
+bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
+ Val &V = Vals[ValNo];
+ if (V.Pruned || V.PrunedComputed)
+ return V.Pruned;
+
+ if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
+ return V.Pruned;
+
+ // Follow copies up the dominator tree and check if any intermediate value
+ // has been pruned.
+ V.PrunedComputed = true;
+ V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
+ return V.Pruned;
+}
+
void JoinVals::pruneValues(JoinVals &Other,
SmallVectorImpl<SlotIndex> &EndPoints) {
for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
- if (Vals[i].Resolution != CR_Replace)
- continue;
SlotIndex Def = LI.getValNumInfo(i)->def;
- LIS->pruneValue(&Other.LI, Def, &EndPoints);
- DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def
- << ": " << Other.LI << '\n');
+ switch (Vals[i].Resolution) {
+ case CR_Keep:
+ break;
+ case CR_Replace: {
+ // This value takes precedence over the value in Other.LI.
+ LIS->pruneValue(&Other.LI, Def, &EndPoints);
+ // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF
+ // instructions are only inserted to provide a live-out value for PHI
+ // predecessors, so the instruction should simply go away once its value
+ // has been replaced.
+ Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
+ bool EraseImpDef = OtherV.IsImplicitDef && OtherV.Resolution == CR_Keep;
+ if (!Def.isBlock()) {
+ // Remove <def,read-undef> flags. This def is now a partial redef.
+ // Also remove <def,dead> flags since the joined live range will
+ // continue past this instruction.
+ for (MIOperands MO(Indexes->getInstructionFromIndex(Def));
+ MO.isValid(); ++MO)
+ if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) {
+ MO->setIsUndef(EraseImpDef);
+ MO->setIsDead(false);
+ }
+ // This value will reach instructions below, but we need to make sure
+ // the live range also reaches the instruction at Def.
+ if (!EraseImpDef)
+ EndPoints.push_back(Def);
+ }
+ DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def
+ << ": " << Other.LI << '\n');
+ break;
+ }
+ case CR_Erase:
+ case CR_Merge:
+ if (isPrunedValue(i, Other)) {
+ // This value is ultimately a copy of a pruned value in LI or Other.LI.
+ // We can no longer trust the value mapping computed by
+ // computeAssignment(), the value that was originally copied could have
+ // been replaced.
+ LIS->pruneValue(&LI, Def, &EndPoints);
+ DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at "
+ << Def << ": " << LI << '\n');
+ }
+ break;
+ case CR_Unresolved:
+ case CR_Impossible:
+ llvm_unreachable("Unresolved conflicts");
+ }
}
}
void JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs,
SmallVectorImpl<unsigned> &ShrinkRegs) {
for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
- if (Vals[i].Resolution != CR_Erase)
- continue;
+ // Get the def location before markUnused() below invalidates it.
SlotIndex Def = LI.getValNumInfo(i)->def;
- MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
- assert(MI && "No instruction to erase");
- if (MI->isCopy()) {
- unsigned Reg = MI->getOperand(1).getReg();
- if (TargetRegisterInfo::isVirtualRegister(Reg) &&
- Reg != CP.getSrcReg() && Reg != CP.getDstReg())
- ShrinkRegs.push_back(Reg);
+ switch (Vals[i].Resolution) {
+ case CR_Keep:
+ // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
+ // longer. The IMPLICIT_DEF instructions are only inserted by
+ // PHIElimination to guarantee that all PHI predecessors have a value.
+ if (!Vals[i].IsImplicitDef || !Vals[i].Pruned)
+ break;
+ // Remove value number i from LI. Note that this VNInfo is still present
+ // in NewVNInfo, so it will appear as an unused value number in the final
+ // joined interval.
+ LI.getValNumInfo(i)->markUnused();
+ LI.removeValNo(LI.getValNumInfo(i));
+ DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n');
+ // FALL THROUGH.
+
+ case CR_Erase: {
+ MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
+ assert(MI && "No instruction to erase");
+ if (MI->isCopy()) {
+ unsigned Reg = MI->getOperand(1).getReg();
+ if (TargetRegisterInfo::isVirtualRegister(Reg) &&
+ Reg != CP.getSrcReg() && Reg != CP.getDstReg())
+ ShrinkRegs.push_back(Reg);
+ }
+ ErasedInstrs.insert(MI);
+ DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
+ LIS->RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ break;
+ }
+ default:
+ break;
}
- ErasedInstrs.insert(MI);
- DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI);
- LIS->RemoveMachineInstrFromMaps(MI);
- MI->eraseFromParent();
}
}
return true;
}
-/// ComputeUltimateVN - Assuming we are going to join two live intervals,
-/// compute what the resultant value numbers for each value in the input two
-/// ranges will be. This is complicated by copies between the two which can
-/// and will commonly cause multiple value numbers to be merged into one.
-///
-/// VN is the value number that we're trying to resolve. InstDefiningValue
-/// keeps track of the new InstDefiningValue assignment for the result
-/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of
-/// whether a value in this or other is a copy from the opposite set.
-/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
-/// already been assigned.
-///
-/// ThisFromOther[x] - If x is defined as a copy from the other interval, this
-/// contains the value number the copy is from.
-///
-static unsigned ComputeUltimateVN(VNInfo *VNI,
- SmallVector<VNInfo*, 16> &NewVNInfo,
- DenseMap<VNInfo*, VNInfo*> &ThisFromOther,
- DenseMap<VNInfo*, VNInfo*> &OtherFromThis,
- SmallVector<int, 16> &ThisValNoAssignments,
- SmallVector<int, 16> &OtherValNoAssignments) {
- unsigned VN = VNI->id;
-
- // If the VN has already been computed, just return it.
- if (ThisValNoAssignments[VN] >= 0)
- return ThisValNoAssignments[VN];
- assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers");
-
- // If this val is not a copy from the other val, then it must be a new value
- // number in the destination.
- DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI);
- if (I == ThisFromOther.end()) {
- NewVNInfo.push_back(VNI);
- return ThisValNoAssignments[VN] = NewVNInfo.size()-1;
- }
- VNInfo *OtherValNo = I->second;
-
- // Otherwise, this *is* a copy from the RHS. If the other side has already
- // been computed, return it.
- if (OtherValNoAssignments[OtherValNo->id] >= 0)
- return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id];
-
- // Mark this value number as currently being computed, then ask what the
- // ultimate value # of the other value is.
- ThisValNoAssignments[VN] = -2;
- unsigned UltimateVN =
- ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther,
- OtherValNoAssignments, ThisValNoAssignments);
- return ThisValNoAssignments[VN] = UltimateVN;
-}
-
-
-// Find out if we have something like
-// A = X
-// B = X
-// if so, we can pretend this is actually
-// A = X
-// B = A
-// which allows us to coalesce A and B.
-// VNI is the definition of B. LR is the life range of A that includes
-// the slot just before B. If we return true, we add "B = X" to DupCopies.
-// This implies that A dominates B.
-static bool RegistersDefinedFromSameValue(LiveIntervals &li,
- const TargetRegisterInfo &tri,
- CoalescerPair &CP,
- VNInfo *VNI,
- VNInfo *OtherVNI,
- SmallVector<MachineInstr*, 8> &DupCopies) {
- // FIXME: This is very conservative. For example, we don't handle
- // physical registers.
-
- MachineInstr *MI = li.getInstructionFromIndex(VNI->def);
-
- if (!MI || CP.isPartial() || CP.isPhys())
- return false;
-
- unsigned A = CP.getDstReg();
- if (!TargetRegisterInfo::isVirtualRegister(A))
- return false;
-
- unsigned B = CP.getSrcReg();
- if (!TargetRegisterInfo::isVirtualRegister(B))
- return false;
-
- MachineInstr *OtherMI = li.getInstructionFromIndex(OtherVNI->def);
- if (!OtherMI)
- return false;
-
- if (MI->isImplicitDef()) {
- DupCopies.push_back(MI);
- return true;
- } else {
- if (!MI->isFullCopy())
- return false;
- unsigned Src = MI->getOperand(1).getReg();
- if (!TargetRegisterInfo::isVirtualRegister(Src))
- return false;
- if (!OtherMI->isFullCopy())
- return false;
- unsigned OtherSrc = OtherMI->getOperand(1).getReg();
- if (!TargetRegisterInfo::isVirtualRegister(OtherSrc))
- return false;
-
- if (Src != OtherSrc)
- return false;
-
- // If the copies use two different value numbers of X, we cannot merge
- // A and B.
- LiveInterval &SrcInt = li.getInterval(Src);
- // getVNInfoBefore returns NULL for undef copies. In this case, the
- // optimization is still safe.
- if (SrcInt.getVNInfoBefore(OtherVNI->def) !=
- SrcInt.getVNInfoBefore(VNI->def))
- return false;
-
- DupCopies.push_back(MI);
- return true;
- }
-}
-
/// joinIntervals - Attempt to join these two intervals. On failure, this
/// returns false.
bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
- // Handle physreg joins separately.
- if (CP.isPhys())
- return joinReservedPhysReg(CP);
-
- if (NewCoalescer)
- return joinVirtRegs(CP);
-
- LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
- DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS
- << '\n');
-
- // Compute the final value assignment, assuming that the live ranges can be
- // coalesced.
- SmallVector<int, 16> LHSValNoAssignments;
- SmallVector<int, 16> RHSValNoAssignments;
- DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS;
- DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS;
- SmallVector<VNInfo*, 16> NewVNInfo;
-
- SmallVector<MachineInstr*, 8> DupCopies;
- SmallVector<MachineInstr*, 8> DeadCopies;
-
- LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg());
- DEBUG(dbgs() << "\t\tLHS = " << PrintReg(CP.getDstReg(), TRI) << ' ' << LHS
- << '\n');
-
- // Loop over the value numbers of the LHS, seeing if any are defined from
- // the RHS.
- for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
- i != e; ++i) {
- VNInfo *VNI = *i;
- if (VNI->isUnused() || VNI->isPHIDef())
- continue;
- MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def);
- assert(MI && "Missing def");
- if (!MI->isCopyLike() && !MI->isImplicitDef()) // Src not defined by a copy?
- continue;
-
- // Figure out the value # from the RHS.
- VNInfo *OtherVNI = RHS.getVNInfoBefore(VNI->def);
- // The copy could be to an aliased physreg.
- if (!OtherVNI)
- continue;
-
- // DstReg is known to be a register in the LHS interval. If the src is
- // from the RHS interval, we can use its value #.
- if (CP.isCoalescable(MI))
- DeadCopies.push_back(MI);
- else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI,
- DupCopies))
- continue;
-
- LHSValsDefinedFromRHS[VNI] = OtherVNI;
- }
-
- // Loop over the value numbers of the RHS, seeing if any are defined from
- // the LHS.
- for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
- i != e; ++i) {
- VNInfo *VNI = *i;
- if (VNI->isUnused() || VNI->isPHIDef())
- continue;
- MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def);
- assert(MI && "Missing def");
- if (!MI->isCopyLike() && !MI->isImplicitDef()) // Src not defined by a copy?
- continue;
-
- // Figure out the value # from the LHS.
- VNInfo *OtherVNI = LHS.getVNInfoBefore(VNI->def);
- // The copy could be to an aliased physreg.
- if (!OtherVNI)
- continue;
-
- // DstReg is known to be a register in the RHS interval. If the src is
- // from the LHS interval, we can use its value #.
- if (CP.isCoalescable(MI))
- DeadCopies.push_back(MI);
- else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI,
- DupCopies))
- continue;
-
- RHSValsDefinedFromLHS[VNI] = OtherVNI;
- }
-
- LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
- RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
- NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
-
- for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end();
- i != e; ++i) {
- VNInfo *VNI = *i;
- unsigned VN = VNI->id;
- if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused())
- continue;
- ComputeUltimateVN(VNI, NewVNInfo,
- LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
- LHSValNoAssignments, RHSValNoAssignments);
- }
- for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end();
- i != e; ++i) {
- VNInfo *VNI = *i;
- unsigned VN = VNI->id;
- if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused())
- continue;
- // If this value number isn't a copy from the LHS, it's a new number.
- if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) {
- NewVNInfo.push_back(VNI);
- RHSValNoAssignments[VN] = NewVNInfo.size()-1;
- continue;
- }
-
- ComputeUltimateVN(VNI, NewVNInfo,
- RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
- RHSValNoAssignments, LHSValNoAssignments);
- }
-
- // Armed with the mappings of LHS/RHS values to ultimate values, walk the
- // interval lists to see if these intervals are coalescable.
- LiveInterval::const_iterator I = LHS.begin();
- LiveInterval::const_iterator IE = LHS.end();
- LiveInterval::const_iterator J = RHS.begin();
- LiveInterval::const_iterator JE = RHS.end();
-
- // Collect interval end points that will no longer be kills.
- SmallVector<MachineInstr*, 8> LHSOldKills;
- SmallVector<MachineInstr*, 8> RHSOldKills;
-
- // Skip ahead until the first place of potential sharing.
- if (I != IE && J != JE) {
- if (I->start < J->start) {
- I = std::upper_bound(I, IE, J->start);
- if (I != LHS.begin()) --I;
- } else if (J->start < I->start) {
- J = std::upper_bound(J, JE, I->start);
- if (J != RHS.begin()) --J;
- }
- }
-
- while (I != IE && J != JE) {
- // Determine if these two live ranges overlap.
- // If so, check value # info to determine if they are really different.
- if (I->end > J->start && J->end > I->start) {
- // If the live range overlap will map to the same value number in the
- // result liverange, we can still coalesce them. If not, we can't.
- if (LHSValNoAssignments[I->valno->id] !=
- RHSValNoAssignments[J->valno->id])
- return false;
-
- // Extended live ranges should no longer be killed.
- if (!I->end.isBlock() && I->end < J->end)
- if (MachineInstr *MI = LIS->getInstructionFromIndex(I->end))
- LHSOldKills.push_back(MI);
- if (!J->end.isBlock() && J->end < I->end)
- if (MachineInstr *MI = LIS->getInstructionFromIndex(J->end))
- RHSOldKills.push_back(MI);
- }
-
- if (I->end < J->end)
- ++I;
- else
- ++J;
- }
-
- // Clear kill flags where live ranges are extended.
- while (!LHSOldKills.empty())
- LHSOldKills.pop_back_val()->clearRegisterKills(LHS.reg, TRI);
- while (!RHSOldKills.empty())
- RHSOldKills.pop_back_val()->clearRegisterKills(RHS.reg, TRI);
-
- if (LHSValNoAssignments.empty())
- LHSValNoAssignments.push_back(-1);
- if (RHSValNoAssignments.empty())
- RHSValNoAssignments.push_back(-1);
-
- // Now erase all the redundant copies.
- for (unsigned i = 0, e = DeadCopies.size(); i != e; ++i) {
- MachineInstr *MI = DeadCopies[i];
- if (!ErasedInstrs.insert(MI))
- continue;
- DEBUG(dbgs() << "\t\terased:\t" << LIS->getInstructionIndex(MI)
- << '\t' << *MI);
- LIS->RemoveMachineInstrFromMaps(MI);
- MI->eraseFromParent();
- }
-
- SmallVector<unsigned, 8> SourceRegisters;
- for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(),
- E = DupCopies.end(); I != E; ++I) {
- MachineInstr *MI = *I;
- if (!ErasedInstrs.insert(MI))
- continue;
-
- // If MI is a copy, then we have pretended that the assignment to B in
- // A = X
- // B = X
- // was actually a copy from A. Now that we decided to coalesce A and B,
- // transform the code into
- // A = X
- // In the case of the implicit_def, we just have to remove it.
- if (!MI->isImplicitDef()) {
- unsigned Src = MI->getOperand(1).getReg();
- SourceRegisters.push_back(Src);
- }
- LIS->RemoveMachineInstrFromMaps(MI);
- MI->eraseFromParent();
- }
-
- // If B = X was the last use of X in a liverange, we have to shrink it now
- // that B = X is gone.
- for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(),
- E = SourceRegisters.end(); I != E; ++I) {
- LIS->shrinkToUses(&LIS->getInterval(*I));
- }
-
- // If we get here, we know that we can coalesce the live ranges. Ask the
- // intervals to coalesce themselves now.
- LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo,
- MRI);
- return true;
+ return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
}
namespace {
- // DepthMBBCompare - Comparison predicate that sort first based on the loop
- // depth of the basic block (the unsigned), and then on the MBB number.
- struct DepthMBBCompare {
- typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair;
- bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const {
+ // Information concerning MBB coalescing priority.
+ struct MBBPriorityInfo {
+ MachineBasicBlock *MBB;
+ unsigned Depth;
+ bool IsSplit;
+
+ MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
+ : MBB(mbb), Depth(depth), IsSplit(issplit) {}
+ };
+
+ // MBBPriorityCompare - Comparison predicate that sorts first based on the
+ // loop depth of the basic block (the unsigned), and then on the MBB number.
+ struct MBBPriorityCompare {
+ bool operator()(const MBBPriorityInfo &LHS,
+ const MBBPriorityInfo &RHS) const {
// Deeper loops first
- if (LHS.first != RHS.first)
- return LHS.first > RHS.first;
+ if (LHS.Depth != RHS.Depth)
+ return LHS.Depth > RHS.Depth;
+
+ // Try to unsplit critical edges next.
+ if (EnableJoinSplits && LHS.IsSplit != RHS.IsSplit)
+ return LHS.IsSplit;
// Prefer blocks that are more connected in the CFG. This takes care of
// the most difficult copies first while intervals are short.
- unsigned cl = LHS.second->pred_size() + LHS.second->succ_size();
- unsigned cr = RHS.second->pred_size() + RHS.second->succ_size();
+ unsigned cl = LHS.MBB->pred_size() + LHS.MBB->succ_size();
+ unsigned cr = RHS.MBB->pred_size() + RHS.MBB->succ_size();
if (cl != cr)
return cl > cr;
// As a last resort, sort by block number.
- return LHS.second->getNumber() < RHS.second->getNumber();
+ return LHS.MBB->getNumber() < RHS.MBB->getNumber();
}
};
}
DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n");
assert(WorkList.empty() && "Old data still around.");
- if (Loops->empty()) {
- // If there are no loops in the function, join intervals in function order.
- for (MachineFunction::iterator I = MF->begin(), E = MF->end();
- I != E; ++I)
- copyCoalesceInMBB(I);
- } else {
- // Otherwise, join intervals in inner loops before other intervals.
- // Unfortunately we can't just iterate over loop hierarchy here because
- // there may be more MBB's than BB's. Collect MBB's for sorting.
-
- // Join intervals in the function prolog first. We want to join physical
- // registers with virtual registers before the intervals got too long.
- std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs;
- for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){
- MachineBasicBlock *MBB = I;
- MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I));
- }
-
- // Sort by loop depth.
- std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare());
-
- // Finally, join intervals in loop nest order.
- for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
- copyCoalesceInMBB(MBBs[i].second);
+ std::vector<MBBPriorityInfo> MBBs;
+ for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){
+ MachineBasicBlock *MBB = I;
+ MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB),
+ isSplitEdge(MBB)));
}
+ std::sort(MBBs.begin(), MBBs.end(), MBBPriorityCompare());
+
+ // Coalesce intervals in MBB priority order.
+ for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
+ copyCoalesceInMBB(MBBs[i].MBB);
// Joining intervals can allow other intervals to be joined. Iteratively join
// until we make no progress.
projects / oota-llvm.git / blobdiff