X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterCoalescer.cpp;h=1b46256baf2b14ff1adc34e44a642a3cec42ba0d;hb=be9262b8c7d32b416893368061281f827b489b18;hp=67cad14afd3aaead0bbf014031d35b0c4f1377be;hpb=87f7864c6d81ae134335b8271ac12c937c81dffc;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp index 67cad14afd3..1b46256baf2 100644 --- a/lib/CodeGen/RegisterCoalescer.cpp +++ b/lib/CodeGen/RegisterCoalescer.cpp @@ -55,6 +55,8 @@ STATISTIC(numCommutes , "Number of instruction commuting performed"); 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 EnableJoining("join-liveintervals", @@ -66,11 +68,6 @@ 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 -NewCoalescer("new-coalescer", cl::Hidden, - cl::desc("Use new coalescer algorithm")); - namespace { class RegisterCoalescer : public MachineFunctionPass, private LiveRangeEdit::Delegate { @@ -1244,8 +1241,15 @@ class JoinVals { // Value in the other live range that overlaps this def, if any. VNInfo *OtherVNI; + // 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), Pruned(false), PrunedComputed(false) {} bool isAnalyzed() const { return WriteLanes != 0; } }; @@ -1257,6 +1261,10 @@ class JoinVals { VNInfo *stripCopies(VNInfo *VNI); ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); void computeAssignment(unsigned ValNo, JoinVals &Other); + bool taintExtent(unsigned, unsigned, JoinVals&, + SmallVectorImpl >&); + bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); + bool isPrunedValue(unsigned ValNo, JoinVals &Other); public: JoinVals(LiveInterval &li, unsigned subIdx, @@ -1389,7 +1397,6 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { // 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 @@ -1407,10 +1414,14 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { // 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; } @@ -1428,9 +1439,10 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 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()) @@ -1474,9 +1486,28 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { if ((V.WriteLanes & OtherV.ValidLanes) == 0) return CR_Replace; - // FIXME: Identify CR_Replace opportunities where the clobbered lanes are - // dead. - 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. @@ -1503,6 +1534,12 @@ void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { << 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(); @@ -1523,28 +1560,202 @@ bool JoinVals::mapValues(JoinVals &Other) { 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 > &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(compose(*TRI, 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, 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 &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); + // Remove flags. This def is now a partial redef. + if (!Def.isBlock()) { + for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); + MO.isValid(); ++MO) + if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) + MO->setIsUndef(false); + // This value will reach instructions below, but we need to make sure + // the live range also reaches the instruction at Def. + 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"); + } } } @@ -1628,348 +1839,10 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 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 &NewVNInfo, - DenseMap &ThisFromOther, - DenseMap &OtherFromThis, - SmallVector &ThisValNoAssignments, - SmallVector &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::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 &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 LHSValNoAssignments; - SmallVector RHSValNoAssignments; - DenseMap LHSValsDefinedFromRHS; - DenseMap RHSValsDefinedFromLHS; - SmallVector NewVNInfo; - - SmallVector DupCopies; - SmallVector 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 LHSOldKills; - SmallVector 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 SourceRegisters; - for (SmallVector::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::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 {