/// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.
/// Subranges in @p LI which only partially interfere with the desired
- /// LaneMask are split as necessary.
+ /// LaneMask are split as necessary. @p LaneMask are the lanes that
+ /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
+ /// lanemasks already adjusted to the coalesced register.
void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
unsigned LaneMask, CoalescerPair &CP);
/// Join the liveranges of two subregisters. Joins @p RRange into
/// @p LRange, @p RRange may be invalid afterwards.
void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
- const CoalescerPair &CP);
+ unsigned LaneMask, const CoalescerPair &CP);
/// We found a non-trivially-coalescable copy. If
/// the source value number is defined by a copy from the destination reg
void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx);
/// Handle copies of undef values.
- bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP);
+ bool eliminateUndefCopy(MachineInstr *CopyMI);
public:
static char ID; // Class identification, replacement for typeinfo
IntB.MergeValueNumberInto(BValNo, ValS->valno);
// Do the same for the subregister segments.
- for (LiveInterval::subrange_iterator S = IntB.subrange_begin(),
- SE = IntB.subrange_end(); S != SE; ++S) {
- VNInfo *SubBValNo = S->getVNInfoAt(CopyIdx);
- S->addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
- VNInfo *SubValSNo = S->getVNInfoAt(AValNo->def.getPrevSlot());
+ for (LiveInterval::SubRange &S : IntB.subranges()) {
+ VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
+ S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
+ VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());
if (SubBValNo != SubValSNo)
- S->MergeValueNumberInto(SubBValNo, SubValSNo);
+ S.MergeValueNumberInto(SubBValNo, SubValSNo);
}
DEBUG(dbgs() << " result = " << IntB << '\n');
///
/// B2 = op B0 A2<kill>
/// ...
-/// B1 = B2 <- now an identify copy
+/// B1 = B2 <- now an identity copy
/// ...
/// = op B2 <- more uses
///
///
bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
MachineInstr *CopyMI) {
- assert (!CP.isPhys());
-
- SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
+ assert(!CP.isPhys());
LiveInterval &IntA =
- LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
+ LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
LiveInterval &IntB =
- LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
+ LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
// BValNo is a value number in B that is defined by a copy from A. 'B1' in
// the example above.
+ SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx);
- if (!BValNo || BValNo->def != CopyIdx)
- return false;
+ assert(BValNo != nullptr && BValNo->def == CopyIdx);
// AValNo is the value number in A that defines the copy, A3 in the example.
VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true));
- assert(AValNo && "COPY source not live");
- if (AValNo->isPHIDef() || AValNo->isUnused())
+ assert(AValNo && !AValNo->isUnused() && "COPY source not live");
+ if (AValNo->isPHIDef())
return false;
MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def);
if (!DefMI)
MBB->insert(Pos, NewMI);
MBB->erase(DefMI);
}
- unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
- NewMI->getOperand(OpIdx).setIsKill();
// If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
// A = or A, B
// Update uses of IntA of the specific Val# with IntB.
for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg),
- UE = MRI->use_end(); UI != UE;) {
+ UE = MRI->use_end();
+ UI != UE; /* ++UI is below because of possible MI removal */) {
MachineOperand &UseMO = *UI;
- MachineInstr *UseMI = UseMO.getParent();
++UI;
+ if (UseMO.isUndef())
+ continue;
+ MachineInstr *UseMI = UseMO.getParent();
if (UseMI->isDebugValue()) {
// FIXME These don't have an instruction index. Not clear we have enough
// info to decide whether to do this replacement or not. For now do it.
}
SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true);
LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
- if (US == IntA.end() || US->valno != AValNo)
+ assert(US != IntA.end() && "Use must be live");
+ if (US->valno != AValNo)
continue;
// Kill flags are no longer accurate. They are recomputed after RA.
UseMO.setIsKill(false);
DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI);
assert(DVNI->def == DefIdx);
BValNo = IntB.MergeValueNumberInto(BValNo, DVNI);
- for (LiveInterval::subrange_iterator S = IntB.subrange_begin(),
- SE = IntB.subrange_end(); S != SE; ++S) {
- VNInfo *SubDVNI = S->getVNInfoAt(DefIdx);
+ for (LiveInterval::SubRange &S : IntB.subranges()) {
+ VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
if (!SubDVNI)
continue;
- VNInfo *SubBValNo = S->getVNInfoAt(CopyIdx);
- S->MergeValueNumberInto(SubBValNo, SubDVNI);
+ VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
+ assert(SubBValNo->def == CopyIdx);
+ VNInfo *Merged = S.MergeValueNumberInto(SubBValNo, SubDVNI);
+ Merged->def = CopyIdx;
}
ErasedInstrs.insert(UseMI);
IntA.createSubRangeFrom(Allocator, Mask, IntA);
}
SlotIndex AIdx = CopyIdx.getRegSlot(true);
- for (LiveInterval::subrange_iterator SA = IntA.subrange_begin(),
- SAE = IntA.subrange_end(); SA != SAE; ++SA) {
- VNInfo *ASubValNo = SA->getVNInfoAt(AIdx);
- if (ASubValNo == nullptr) {
- DEBUG(dbgs() << "No A Range at " << AIdx << " with mask "
- << format("%04X", SA->LaneMask) << "\n");
- continue;
- }
+ for (LiveInterval::SubRange &SA : IntA.subranges()) {
+ VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
+ assert(ASubValNo != nullptr);
- unsigned AMask = SA->LaneMask;
- for (LiveInterval::subrange_iterator SB = IntB.subrange_begin(),
- SBE = IntB.subrange_end(); SB != SBE; ++SB) {
- unsigned BMask = SB->LaneMask;
+ unsigned AMask = SA.LaneMask;
+ for (LiveInterval::SubRange &SB : IntB.subranges()) {
+ unsigned BMask = SB.LaneMask;
unsigned Common = BMask & AMask;
if (Common == 0)
continue;
- DEBUG(dbgs() << format("\t\tCopy+Merge %04X into %04X\n", BMask, Common));
+ DEBUG(
+ dbgs() << format("\t\tCopy+Merge %04X into %04X\n", BMask, Common));
unsigned BRest = BMask & ~AMask;
LiveInterval::SubRange *CommonRange;
if (BRest != 0) {
- SB->LaneMask = BRest;
+ SB.LaneMask = BRest;
DEBUG(dbgs() << format("\t\tReduce Lane to %04X\n", BRest));
// Duplicate SubRange for newly merged common stuff.
- CommonRange = IntB.createSubRangeFrom(Allocator, Common, *SB);
+ CommonRange = IntB.createSubRangeFrom(Allocator, Common, SB);
} else {
// We van reuse the L SubRange.
- SB->LaneMask = Common;
- CommonRange = &*SB;
+ SB.LaneMask = Common;
+ CommonRange = &SB;
}
- LiveRange RangeCopy(*SB, Allocator);
+ LiveRange RangeCopy(SB, Allocator);
VNInfo *BSubValNo = CommonRange->getVNInfoAt(CopyIdx);
assert(BSubValNo->def == CopyIdx);
BSubValNo->def = ASubValNo->def;
- addSegmentsWithValNo(*CommonRange, BSubValNo, *SA, ASubValNo);
+ addSegmentsWithValNo(*CommonRange, BSubValNo, SA, ASubValNo);
AMask &= ~BMask;
}
if (AMask != 0) {
DEBUG(dbgs() << format("\t\tNew Lane %04X\n", AMask));
LiveRange *NewRange = IntB.createSubRange(Allocator, AMask);
VNInfo *BSubValNo = NewRange->getNextValue(CopyIdx, Allocator);
- addSegmentsWithValNo(*NewRange, BSubValNo, *SA, ASubValNo);
- }
- SA->removeValNo(ASubValNo);
- }
- } else if (IntA.hasSubRanges()) {
- SlotIndex AIdx = CopyIdx.getRegSlot(true);
- for (LiveInterval::subrange_iterator SA = IntA.subrange_begin(),
- SAE = IntA.subrange_end(); SA != SAE; ++SA) {
- VNInfo *ASubValNo = SA->getVNInfoAt(AIdx);
- if (ASubValNo == nullptr) {
- DEBUG(dbgs() << "No A Range at " << AIdx << " with mask "
- << format("%04X", SA->LaneMask) << "\n");
- continue;
+ addSegmentsWithValNo(*NewRange, BSubValNo, SA, ASubValNo);
}
- SA->removeValNo(ASubValNo);
+ SA.removeValNo(ASubValNo);
}
}
DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
IntA.removeValNo(AValNo);
+ // Remove valuenos in subranges (the A+B have subranges case has already been
+ // handled above)
+ if (!IntB.hasSubRanges()) {
+ SlotIndex AIdx = CopyIdx.getRegSlot(true);
+ for (LiveInterval::SubRange &SA : IntA.subranges()) {
+ VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
+ assert(ASubValNo != nullptr);
+ SA.removeValNo(ASubValNo);
+ }
+ }
DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n');
++numCommutes;
return true;
return true;
}
+static void removeUndefValue(LiveRange &LR, SlotIndex At)
+{
+ VNInfo *VNInfo = LR.getVNInfoAt(At);
+ assert(VNInfo != nullptr && SlotIndex::isSameInstr(VNInfo->def, At));
+ LR.removeValNo(VNInfo);
+}
+
/// ProcessImpicitDefs may leave some copies of <undef>
/// values, it only removes local variables. When we have a copy like:
///
///
/// We delete the copy and remove the corresponding value number from %vreg1.
/// Any uses of that value number are marked as <undef>.
-bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI,
- const CoalescerPair &CP) {
+bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {
+ // Note that we do not query CoalescerPair here but redo isMoveInstr as the
+ // CoalescerPair may have a new register class with adjusted subreg indices
+ // at this point.
+ unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+ isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
+
SlotIndex Idx = LIS->getInstructionIndex(CopyMI);
- LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg());
- if (SrcInt->liveAt(Idx))
- return false;
- LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg());
- if (DstInt->liveAt(Idx))
+ const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
+ // CopyMI is undef iff SrcReg is not live before the instruction.
+ if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
+ unsigned SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
+ for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
+ if ((SR.LaneMask & SrcMask) == 0)
+ continue;
+ if (SR.liveAt(Idx))
+ return false;
+ }
+ } else if (SrcLI.liveAt(Idx))
return false;
- // No intervals are live-in to CopyMI - it is undef.
- if (CP.isFlipped())
- DstInt = SrcInt;
- SrcInt = nullptr;
+ DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
+ // Remove any DstReg segments starting at the instruction.
+ LiveInterval &DstLI = LIS->getInterval(DstReg);
+ unsigned DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
SlotIndex RegIndex = Idx.getRegSlot();
- VNInfo *DeadVNI = DstInt->getVNInfoAt(RegIndex);
- assert(DeadVNI && "No value defined in DstInt");
- DstInt->removeValNo(DeadVNI);
- // Eliminate the corresponding values in the subregister ranges.
- for (LiveInterval::subrange_iterator S = DstInt->subrange_begin(),
- E = DstInt->subrange_end(); S != E; ++S) {
- VNInfo *DeadVNI = S->getVNInfoAt(RegIndex);
- if (DeadVNI == nullptr)
+ for (LiveInterval::SubRange &SR : DstLI.subranges()) {
+ if ((SR.LaneMask & DstMask) == 0)
continue;
- S->removeValNo(DeadVNI);
+ removeUndefValue(SR, RegIndex);
+
+ DstLI.removeEmptySubRanges();
+ }
+ // Remove value or merge with previous one in case of a subregister def.
+ if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
+ VNInfo *VNInfo = DstLI.getVNInfoAt(RegIndex);
+ DstLI.MergeValueNumberInto(VNInfo, PrevVNI);
+ } else {
+ removeUndefValue(DstLI, RegIndex);
}
- // Find new undef uses.
- for (MachineOperand &MO : MRI->reg_nodbg_operands(DstInt->reg)) {
- if (MO.isDef() || MO.isUndef())
+ // Mark uses as undef.
+ for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {
+ if (MO.isDef() /*|| MO.isUndef()*/)
continue;
- MachineInstr *MI = MO.getParent();
- SlotIndex Idx = LIS->getInstructionIndex(MI);
- if (DstInt->liveAt(Idx))
+ const MachineInstr &MI = *MO.getParent();
+ SlotIndex UseIdx = LIS->getInstructionIndex(&MI);
+ unsigned UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
+ bool isLive;
+ if (UseMask != ~0u && DstLI.hasSubRanges()) {
+ isLive = false;
+ for (const LiveInterval::SubRange &SR : DstLI.subranges()) {
+ if ((SR.LaneMask & UseMask) == 0)
+ continue;
+ if (SR.liveAt(UseIdx)) {
+ isLive = true;
+ break;
+ }
+ }
+ } else
+ isLive = DstLI.liveAt(UseIdx);
+ if (isLive)
continue;
MO.setIsUndef(true);
- DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI);
+ DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI);
}
return true;
}
? LIS->getSlotIndexes()->getIndexBefore(UseMI)
: LIS->getInstructionIndex(UseMI);
SlotIndex UseIdx = MIIdx.getRegSlot(true);
- for (LiveInterval::subrange_iterator S = DstInt->subrange_begin(),
- SE = DstInt->subrange_end(); S != SE; ++S) {
- if ((S->LaneMask & Mask) == 0)
+ for (LiveInterval::SubRange &S : DstInt->subranges()) {
+ if ((S.LaneMask & Mask) == 0)
continue;
- if (S->liveAt(UseIdx)) {
+ if (S.liveAt(UseIdx)) {
IsUndef = false;
break;
}
}
// Eliminate undefs.
- if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) {
- DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n");
+ if (!CP.isPhys() && eliminateUndefCopy(CopyMI)) {
LIS->RemoveMachineInstrFromMaps(CopyMI);
CopyMI->eraseFromParent();
return false; // Not coalescable.
LI.MergeValueNumberInto(DefVNI, ReadVNI);
// Process subregister liveranges.
- for (LiveInterval::subrange_iterator S = LI.subrange_begin(),
- SE = LI.subrange_end(); S != SE; ++S) {
- LiveQueryResult SLRQ = S->Query(CopyIdx);
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ LiveQueryResult SLRQ = S.Query(CopyIdx);
if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
VNInfo *SReadVNI = SLRQ.valueIn();
- S->MergeValueNumberInto(SDefVNI, SReadVNI);
+ S.MergeValueNumberInto(SDefVNI, SReadVNI);
}
}
DEBUG(dbgs() << "\tMerged values: " << LI << '\n');
// Shrink subregister ranges if necessary.
if (ShrinkMask != 0) {
LiveInterval &LI = LIS->getInterval(CP.getDstReg());
- for (LiveInterval::subrange_iterator S = LI.subrange_begin(),
- SE = LI.subrange_end(); S != SE; ++S) {
- if ((S->LaneMask & ShrinkMask) == 0)
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ if ((S.LaneMask & ShrinkMask) == 0)
continue;
DEBUG(dbgs() << "Shrink LaneUses (Lane "
- << format("%04X", S->LaneMask) << ")\n");
- LIS->shrinkToUses(*S, LI.reg);
+ << format("%04X", S.LaneMask) << ")\n");
+ LIS->shrinkToUses(S, LI.reg);
}
}
if (ShrinkMainRange) {
/// Live range we work on.
LiveRange &LR;
/// (Main) register we work on.
- unsigned Reg;
+ const unsigned Reg;
+
+ // Reg (and therefore the values in this liverange) will end up as subregister
+ // SubIdx in the coalesced register. Either CP.DstIdx or CP.SrcIdx.
+ const unsigned SubIdx;
+ // The LaneMask that this liverange will occupy the coalesced register. May be
+ // smaller than the lanemask produced by SubIdx when merging subranges.
+ const unsigned LaneMask;
/// This is true when joining sub register ranges, false when joining main
/// ranges.
- bool SubRangeJoin;
+ const bool SubRangeJoin;
/// Whether the current LiveInterval tracks subregister liveness.
- bool TrackSubRegLiveness;
-
- // Location of this register in the final joined register.
- // Either CP.DstIdx or CP.SrcIdx.
- unsigned SubIdx;
+ const bool TrackSubRegLiveness;
// Values that will be present in the final live range.
SmallVectorImpl<VNInfo*> &NewVNInfo;
// One entry per value number in LI.
SmallVector<Val, 8> Vals;
- unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef);
- VNInfo *stripCopies(VNInfo *VNI);
+ unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
+ std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
+ bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
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 usesLanes(const MachineInstr *MI, unsigned, unsigned, unsigned) const;
bool isPrunedValue(unsigned ValNo, JoinVals &Other);
public:
- JoinVals(LiveRange &LR, unsigned Reg, unsigned subIdx,
- SmallVectorImpl<VNInfo*> &newVNInfo,
- const CoalescerPair &cp, LiveIntervals *lis,
- const TargetRegisterInfo *tri, bool SubRangeJoin,
+ JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, unsigned LaneMask,
+ SmallVectorImpl<VNInfo*> &newVNInfo, const CoalescerPair &cp,
+ LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
bool TrackSubRegLiveness)
- : LR(LR), Reg(Reg), SubRangeJoin(SubRangeJoin),
- TrackSubRegLiveness(TrackSubRegLiveness), SubIdx(subIdx),
+ : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
+ SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
- TRI(tri), Assignments(LR.getNumValNums(), -1),
- Vals(LR.getNumValNums())
+ TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums())
{}
/// Analyze defs in LR and compute a value mapping in NewVNInfo.
/// Compute the bitmask of lanes actually written by DefMI.
/// Set Redef if there are any partial register definitions that depend on the
/// previous value of the register.
-unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) {
+unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
+ const {
unsigned L = 0;
for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) {
if (!MO->isReg() || MO->getReg() != Reg || !MO->isDef())
}
/// Find the ultimate value that VNI was copied from.
-VNInfo *JoinVals::stripCopies(VNInfo *VNI) {
+std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain(
+ const VNInfo *VNI) const {
+ unsigned Reg = this->Reg;
+
while (!VNI->isPHIDef()) {
- MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def);
+ SlotIndex Def = VNI->def;
+ MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
assert(MI && "No defining instruction");
if (!MI->isFullCopy())
+ return std::make_pair(VNI, Reg);
+ unsigned SrcReg = MI->getOperand(1).getReg();
+ if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
+ return std::make_pair(VNI, Reg);
+
+ const LiveInterval &LI = LIS->getInterval(SrcReg);
+ const VNInfo *ValueIn;
+ // No subrange involved.
+ if (!SubRangeJoin || !LI.hasSubRanges()) {
+ LiveQueryResult LRQ = LI.Query(Def);
+ ValueIn = LRQ.valueIn();
+ } else {
+ // Query subranges. Pick the first matching one.
+ ValueIn = nullptr;
+ for (const LiveInterval::SubRange &S : LI.subranges()) {
+ // Transform lanemask to a mask in the joined live interval.
+ unsigned SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
+ if ((SMask & LaneMask) == 0)
+ continue;
+ LiveQueryResult LRQ = S.Query(Def);
+ ValueIn = LRQ.valueIn();
+ break;
+ }
+ }
+ if (ValueIn == nullptr)
break;
- unsigned Reg = MI->getOperand(1).getReg();
- if (!TargetRegisterInfo::isVirtualRegister(Reg))
- break;
- LiveQueryResult LRQ = LIS->getInterval(Reg).Query(VNI->def);
- if (!LRQ.valueIn())
- break;
- VNI = LRQ.valueIn();
+ VNI = ValueIn;
+ Reg = SrcReg;
}
- return VNI;
+ return std::make_pair(VNI, Reg);
+}
+
+bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
+ const JoinVals &Other) const {
+ const VNInfo *Orig0;
+ unsigned Reg0;
+ std::tie(Orig0, Reg0) = followCopyChain(Value0);
+ if (Orig0 == Value1)
+ return true;
+
+ const VNInfo *Orig1;
+ unsigned Reg1;
+ std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
+
+ // The values are equal if they are defined at the same place and use the
+ // same register. Note that we cannot compare VNInfos directly as some of
+ // them might be from a copy created in mergeSubRangeInto() while the other
+ // is from the original LiveInterval.
+ return Orig0->def == Orig1->def && Reg0 == Reg1;
}
/// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
// not important.
if (Redef) {
V.RedefVNI = LR.Query(VNI->def).valueIn();
- assert(V.RedefVNI && "Instruction is reading nonexistent value");
- computeAssignment(V.RedefVNI->id, Other);
- V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
+ assert((TrackSubRegLiveness || V.RedefVNI) &&
+ "Instruction is reading nonexistent value");
+ if (V.RedefVNI != nullptr) {
+ computeAssignment(V.RedefVNI->id, Other);
+ V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
+ }
}
// An IMPLICIT_DEF writes undef values.
return CR_Replace;
// Check for simple erasable conflicts.
- if (DefMI->isImplicitDef())
+ if (DefMI->isImplicitDef()) {
+ // We need the def for the subregister if there is nothing else live at the
+ // subrange at this point.
+ if (TrackSubRegLiveness
+ && (V.WriteLanes & (OtherV.ValidLanes | OtherV.WriteLanes)) == 0)
+ return CR_Replace;
return CR_Erase;
+ }
// Include the non-conflict where DefMI is a coalescable copy that kills
// OtherVNI. We still want the copy erased and value numbers merged.
// %other = COPY %ext
// %this = COPY %ext <-- Erase this copy
//
- if (DefMI->isFullCopy() && !CP.isPartial()) {
- VNInfo *TVNI = stripCopies(VNI);
- VNInfo *OVNI = stripCopies(V.OtherVNI);
- // Map our subrange values to main range as stripCopies() follows the main
- // ranges.
- if (SubRangeJoin && TVNI != OVNI) {
- if (TVNI == VNI) {
- LiveInterval &LI = LIS->getInterval(Reg);
- TVNI = LI.getVNInfoAt(TVNI->def);
- }
- if (OVNI == V.OtherVNI) {
- LiveInterval &LI = LIS->getInterval(Other.Reg);
- OVNI = LI.getVNInfoAt(OVNI->def);
- }
- }
-
- if (TVNI == OVNI)
- return CR_Erase;
- }
-
+ if (DefMI->isFullCopy() && !CP.isPartial()
+ && valuesIdentical(VNI, V.OtherVNI, Other))
+ return CR_Erase;
// If the lanes written by this instruction were all undef in OtherVNI, it is
// still safe to join the live ranges. This can't be done with a simple value
/// 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) {
+bool JoinVals::usesLanes(const MachineInstr *MI, unsigned Reg, unsigned SubIdx,
+ unsigned Lanes) const {
if (MI->isDebugValue())
return false;
for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
// Check subranges at the point where the copy will be removed.
SlotIndex Def = LR.getValNumInfo(i)->def;
- for (LiveInterval::subrange_iterator I = LI.subrange_begin(),
- E = LI.subrange_end(); I != E; ++I) {
- LiveQueryResult Q = I->Query(Def);
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ LiveQueryResult Q = S.Query(Def);
// If a subrange starts at the copy then an undefined value has been
// copied and we must remove that subrange value as well.
VNInfo *ValueOut = Q.valueOutOrDead();
if (ValueOut != nullptr && Q.valueIn() == nullptr) {
- DEBUG(dbgs() << "\t\tPrune sublane " << format("%04X", I->LaneMask)
+ DEBUG(dbgs() << "\t\tPrune sublane " << format("%04X", S.LaneMask)
<< " at " << Def << "\n");
- LIS->pruneValue(*I, Def, nullptr);
+ LIS->pruneValue(S, Def, nullptr);
DidPrune = true;
// Mark value number as unused.
ValueOut->markUnused();
// partially used later. Shrink the subregister range apropriately.
if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
DEBUG(dbgs() << "\t\tDead uses at sublane "
- << format("%04X", I->LaneMask) << " at " << Def << "\n");
- ShrinkMask |= I->LaneMask;
+ << format("%04X", S.LaneMask) << " at " << Def << "\n");
+ ShrinkMask |= S.LaneMask;
}
}
}
}
void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
+ unsigned LaneMask,
const CoalescerPair &CP) {
SmallVector<VNInfo*, 16> NewVNInfo;
- JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(),
+ JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
NewVNInfo, CP, LIS, TRI, true, true);
- JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(),
+ JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
NewVNInfo, CP, LIS, TRI, true, true);
/// Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
const LiveRange &ToMerge,
- unsigned LaneMask,
- CoalescerPair &CP) {
+ unsigned LaneMask, CoalescerPair &CP) {
BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
- for (LiveInterval::subrange_iterator R = LI.subrange_begin(),
- RE = LI.subrange_end(); R != RE; ++R) {
- unsigned RMask = R->LaneMask;
+ for (LiveInterval::SubRange &R : LI.subranges()) {
+ unsigned RMask = R.LaneMask;
// LaneMask of subregisters common to subrange R and ToMerge.
unsigned Common = RMask & LaneMask;
// There is nothing to do without common subregs.
unsigned LRest = RMask & ~LaneMask;
LiveInterval::SubRange *CommonRange;
if (LRest != 0) {
- R->LaneMask = LRest;
+ R.LaneMask = LRest;
DEBUG(dbgs() << format("\t\tReduce Lane to %04X\n", LRest));
// Duplicate SubRange for newly merged common stuff.
- CommonRange = LI.createSubRangeFrom(Allocator, Common, *R);
+ CommonRange = LI.createSubRangeFrom(Allocator, Common, R);
} else {
// Reuse the existing range.
- R->LaneMask = Common;
- CommonRange = &*R;
+ R.LaneMask = Common;
+ CommonRange = &R;
}
LiveRange RangeCopy(ToMerge, Allocator);
- joinSubRegRanges(*CommonRange, RangeCopy, CP);
+ joinSubRegRanges(*CommonRange, RangeCopy, Common, CP);
LaneMask &= ~RMask;
}
LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
bool TrackSubRegLiveness = MRI->tracksSubRegLiveness();
- JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI,
- false, TrackSubRegLiveness);
- JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), NewVNInfo, CP, LIS, TRI,
- false, TrackSubRegLiveness);
+ JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), 0, NewVNInfo, CP, LIS,
+ TRI, false, TrackSubRegLiveness);
+ JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), 0, NewVNInfo, CP, LIS,
+ TRI, false, TrackSubRegLiveness);
DEBUG(dbgs() << "\t\tRHS = " << RHS
<< "\n\t\tLHS = " << LHS
// All clear, the live ranges can be merged.
if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
+
+ // Transform lanemasks from the LHS to masks in the coalesced register and
+ // create initial subranges if necessary.
unsigned DstIdx = CP.getDstIdx();
if (!LHS.hasSubRanges()) {
- unsigned Mask = CP.getNewRC()->getLaneMask();
- unsigned DstMask = TRI->composeSubRegIndexLaneMask(DstIdx, Mask);
+ unsigned Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
+ : TRI->getSubRegIndexLaneMask(DstIdx);
// LHS must support subregs or we wouldn't be in this codepath.
- assert(DstMask != 0);
- LHS.createSubRangeFrom(Allocator, DstMask, LHS);
- DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
- << ' ' << LHS << '\n');
+ assert(Mask != 0);
+ LHS.createSubRangeFrom(Allocator, Mask, LHS);
} else if (DstIdx != 0) {
// Transform LHS lanemasks to new register class if necessary.
- for (LiveInterval::subrange_iterator R = LHS.subrange_begin(),
- RE = LHS.subrange_end(); R != RE; ++R) {
- unsigned DstMask = TRI->composeSubRegIndexLaneMask(DstIdx, R->LaneMask);
- R->LaneMask = DstMask;
+ for (LiveInterval::SubRange &R : LHS.subranges()) {
+ unsigned Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
+ R.LaneMask = Mask;
}
- DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
- << ' ' << LHS << '\n');
}
+ DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
+ << ' ' << LHS << '\n');
+ // Determine lanemasks of RHS in the coalesced register and merge subranges.
unsigned SrcIdx = CP.getSrcIdx();
if (!RHS.hasSubRanges()) {
- unsigned Mask = SrcIdx != 0
- ? TRI->getSubRegIndexLaneMask(SrcIdx)
- : MRI->getMaxLaneMaskForVReg(LHS.reg);
-
- DEBUG(dbgs() << "\t\tRHS Mask: "
- << format("%04X", Mask) << "\n");
+ unsigned Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
+ : TRI->getSubRegIndexLaneMask(SrcIdx);
mergeSubRangeInto(LHS, RHS, Mask, CP);
} else {
// Pair up subranges and merge.
- for (LiveInterval::subrange_iterator R = RHS.subrange_begin(),
- RE = RHS.subrange_end(); R != RE; ++R) {
- unsigned RMask = R->LaneMask;
- if (SrcIdx != 0) {
- // Transform LaneMask of RHS subranges to the ones on LHS.
- RMask = TRI->composeSubRegIndexLaneMask(SrcIdx, RMask);
- DEBUG(dbgs() << "\t\tTransform RHS Mask "
- << format("%04X", R->LaneMask) << " to subreg "
- << TRI->getSubRegIndexName(SrcIdx)
- << " => " << format("%04X", RMask) << "\n");
- }
-
- mergeSubRangeInto(LHS, *R, RMask, CP);
+ for (LiveInterval::SubRange &R : RHS.subranges()) {
+ unsigned Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
+ mergeSubRangeInto(LHS, R, Mask, CP);
}
}
// If subranges are still supported, then the same subregs should still
// be supported.
#ifndef NDEBUG
- for (LiveInterval::subrange_iterator S = LI.subrange_begin(),
- E = LI.subrange_end(); S != E; ++S) {
- assert ((S->LaneMask & ~MaxMask) == 0);
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ assert ((S.LaneMask & ~MaxMask) == 0);
}
#endif
}