cl::desc("Coalesce copies (default=true)"),
cl::init(true));
-// Temporary flag to test critical edge unsplitting.
+static cl::opt<bool> UseTerminalRule("terminal-rule",
+ cl::desc("Apply the terminal rule"),
+ cl::init(false), cl::Hidden);
+
+/// Temporary flag to test critical edge unsplitting.
static cl::opt<bool>
EnableJoinSplits("join-splitedges",
cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden);
-// Temporary flag to test global copy optimization.
+/// Temporary flag to test global copy optimization.
static cl::opt<cl::boolOrDefault>
EnableGlobalCopies("join-globalcopies",
cl::desc("Coalesce copies that span blocks (default=subtarget)"),
AliasAnalysis *AA;
RegisterClassInfo RegClassInfo;
+ /// A LaneMask to remember on which subregister live ranges we need to call
+ /// shrinkToUses() later.
+ LaneBitmask ShrinkMask;
+
+ /// True if the main range of the currently coalesced intervals should be
+ /// checked for smaller live intervals.
+ bool ShrinkMainRange;
+
/// \brief True if the coalescer should aggressively coalesce global copies
/// in favor of keeping local copies.
bool JoinGlobalCopies;
/// Recursively eliminate dead defs in DeadDefs.
void eliminateDeadDefs();
- /// LiveRangeEdit callback.
+ /// LiveRangeEdit callback for eliminateDeadDefs().
void LRE_WillEraseInstruction(MachineInstr *MI) override;
/// Coalesce the LocalWorkList.
/// copies that cannot yet be coalesced into WorkList.
void copyCoalesceInMBB(MachineBasicBlock *MBB);
- /// Try to coalesce all copies in CurrList. Return
- /// true if any progress was made.
+ /// Tries to coalesce all copies in CurrList. Returns true if any progress
+ /// was made.
bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList);
- /// Attempt to join intervals corresponding to SrcReg/DstReg,
- /// which are the src/dst of the copy instruction CopyMI. This returns
- /// true if the copy was successfully coalesced away. If it is not
- /// currently possible to coalesce this interval, but it may be possible if
- /// other things get coalesced, then it returns true by reference in
- /// 'Again'.
+ /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the
+ /// src/dst of the copy instruction CopyMI. This returns true if the copy
+ /// was successfully coalesced away. If it is not currently possible to
+ /// coalesce this interval, but it may be possible if other things get
+ /// coalesced, then it returns true by reference in 'Again'.
bool joinCopy(MachineInstr *TheCopy, bool &Again);
/// Attempt to join these two intervals. On failure, this
/// Attempt joining with a reserved physreg.
bool joinReservedPhysReg(CoalescerPair &CP);
- /// We found a non-trivially-coalescable copy. If
- /// the source value number is defined by a copy from the destination reg
- /// see if we can merge these two destination reg valno# into a single
- /// value number, eliminating a copy.
+ /// 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. @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.
+ /// @returns false if live range conflicts couldn't get resolved.
+ bool mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
+ LaneBitmask LaneMask, CoalescerPair &CP);
+
+ /// Join the liveranges of two subregisters. Joins @p RRange into
+ /// @p LRange, @p RRange may be invalid afterwards.
+ /// @returns false if live range conflicts couldn't get resolved.
+ bool joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
+ LaneBitmask 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 see if we can merge these two
+ /// destination reg valno# into a single value number, eliminating a copy.
+ /// This returns true if an interval was modified.
bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
/// Return true if there are definitions of IntB
/// If the source value number is defined by a commutable instruction and
/// its other operand is coalesced to the copy dest register, see if we
/// can transform the copy into a noop by commuting the definition.
+ /// This returns true if an interval was modified.
bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI);
/// If the source of a copy is defined by a
/// trivial computation, replace the copy by rematerialize the definition.
- bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI,
+ bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI,
bool &IsDefCopy);
- /// Return true if a physreg copy should be joined.
+ /// Return true if a copy involving a physreg should be joined.
bool canJoinPhys(const CoalescerPair &CP);
- /// Replace all defs and uses of SrcReg to DstReg and
- /// update the subregister number if it is not zero. If DstReg is a
- /// physical register and the existing subregister number of the def / use
- /// being updated is not zero, make sure to set it to the correct physical
- /// subregister.
+ /// Replace all defs and uses of SrcReg to DstReg and update the subregister
+ /// number if it is not zero. If DstReg is a physical register and the
+ /// existing subregister number of the def / use being updated is not zero,
+ /// make sure to set it to the correct physical subregister.
void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx);
/// Handle copies of undef values.
- bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP);
+ /// Returns true if @p CopyMI was a copy of an undef value and eliminated.
+ bool eliminateUndefCopy(MachineInstr *CopyMI);
+
+ /// Check whether or not we should apply the terminal rule on the
+ /// destination (Dst) of \p Copy.
+ /// When the terminal rule applies, Copy is not profitable to
+ /// coalesce.
+ /// Dst is terminal if it has exactly one affinity (Dst, Src) and
+ /// at least one interference (Dst, Dst2). If Dst is terminal, the
+ /// terminal rule consists in checking that at least one of
+ /// interfering node, say Dst2, has an affinity of equal or greater
+ /// weight with Src.
+ /// In that case, Dst2 and Dst will not be able to be both coalesced
+ /// with Src. Since Dst2 exposes more coalescing opportunities than
+ /// Dst, we can drop \p Copy.
+ bool applyTerminalRule(const MachineInstr &Copy) const;
+
+ /// Wrapper method for \see LiveIntervals::shrinkToUses.
+ /// This method does the proper fixing of the live-ranges when the afore
+ /// mentioned method returns true.
+ void shrinkToUses(LiveInterval *LI,
+ SmallVectorImpl<MachineInstr * > *Dead = nullptr) {
+ if (LIS->shrinkToUses(LI, Dead)) {
+ /// Check whether or not \p LI is composed by multiple connected
+ /// components and if that is the case, fix that.
+ SmallVector<LiveInterval*, 8> SplitLIs;
+ LIS->splitSeparateComponents(*LI, SplitLIs);
+ }
+ }
public:
- static char ID; // Class identification, replacement for typeinfo
+ static char ID; ///< Class identification, replacement for typeinfo
RegisterCoalescer() : MachineFunctionPass(ID) {
initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
}
/// Implement the dump method.
void print(raw_ostream &O, const Module* = nullptr) const override;
};
-} /// end anonymous namespace
+} // end anonymous namespace
char &llvm::RegisterCoalescerID = RegisterCoalescer::ID;
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing",
"Simple Register Coalescing", false, false)
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.
+/// 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;
void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
AU.addPreserved<SlotIndexes>();
nullptr, this).eliminateDeadDefs(DeadDefs);
}
-// Callback from eliminateDeadDefs().
void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {
// MI may be in WorkList. Make sure we don't visit it.
ErasedInstrs.insert(MI);
}
-/// We found a non-trivially-coalescable copy with IntA
-/// being the source and IntB being the dest, thus this defines a value number
-/// in IntB. If the source value number (in IntA) is defined by a copy from B,
-/// see if we can merge these two pieces of B into a single value number,
-/// eliminating a copy. For example:
-///
-/// A3 = B0
-/// ...
-/// B1 = A3 <- this copy
-///
-/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
-/// value number to be replaced with B0 (which simplifies the B liveinterval).
-///
-/// This returns true if an interval was modified.
-///
bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
MachineInstr *CopyMI) {
assert(!CP.isPartial() && "This doesn't work for partial copies.");
LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
+ // We have a non-trivially-coalescable copy with IntA being the source and
+ // IntB being the dest, thus this defines a value number in IntB. If the
+ // source value number (in IntA) is defined by a copy from B, see if we can
+ // merge these two pieces of B into a single value number, eliminating a copy.
+ // For example:
+ //
+ // A3 = B0
+ // ...
+ // B1 = A3 <- this copy
+ //
+ // In this case, B0 can be extended to where the B1 copy lives, allowing the
+ // B1 value number to be replaced with B0 (which simplifies the B
+ // liveinterval).
+
// BValNo is a value number in B that is defined by a copy from A. 'B1' in
// the example above.
LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx);
// Okay, merge "B1" into the same value number as "B0".
if (BValNo != ValS->valno)
IntB.MergeValueNumberInto(BValNo, ValS->valno);
+
+ // Do the same for the subregister segments.
+ 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);
+ }
+
DEBUG(dbgs() << " result = " << IntB << '\n');
// If the source instruction was killing the source register before the
// will also add the isKill marker.
CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI);
if (AS->end == CopyIdx)
- LIS->shrinkToUses(&IntA);
+ shrinkToUses(&IntA);
++numExtends;
return true;
}
-/// Return true if there are definitions of IntB
-/// other than BValNo val# that can reach uses of AValno val# of IntA.
bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,
LiveInterval &IntB,
VNInfo *AValNo,
if (LIS->hasPHIKill(IntA, AValNo))
return true;
- for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
- AI != AE; ++AI) {
- if (AI->valno != AValNo) continue;
+ for (LiveRange::Segment &ASeg : IntA.segments) {
+ if (ASeg.valno != AValNo) continue;
LiveInterval::iterator BI =
- std::upper_bound(IntB.begin(), IntB.end(), AI->start);
+ std::upper_bound(IntB.begin(), IntB.end(), ASeg.start);
if (BI != IntB.begin())
--BI;
- for (; BI != IntB.end() && AI->end >= BI->start; ++BI) {
+ for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {
if (BI->valno == BValNo)
continue;
- if (BI->start <= AI->start && BI->end > AI->start)
+ if (BI->start <= ASeg.start && BI->end > ASeg.start)
return true;
- if (BI->start > AI->start && BI->start < AI->end)
+ if (BI->start > ASeg.start && BI->start < ASeg.end)
return true;
}
}
return false;
}
-/// We found a non-trivially-coalescable copy with
-/// IntA being the source and IntB being the dest, thus this defines a value
-/// number in IntB. If the source value number (in IntA) is defined by a
-/// commutable instruction and its other operand is coalesced to the copy dest
-/// register, see if we can transform the copy into a noop by commuting the
-/// definition. For example,
-///
-/// A3 = op A2 B0<kill>
-/// ...
-/// B1 = A3 <- this copy
-/// ...
-/// = op A3 <- more uses
-///
-/// ==>
-///
-/// B2 = op B0 A2<kill>
-/// ...
-/// B1 = B2 <- now an identify copy
-/// ...
-/// = op B2 <- more uses
-///
-/// This returns true if an interval was modified.
-///
+/// Copy segements with value number @p SrcValNo from liverange @p Src to live
+/// range @Dst and use value number @p DstValNo there.
+static void addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo,
+ const LiveRange &Src, const VNInfo *SrcValNo)
+{
+ for (const LiveRange::Segment &S : Src.segments) {
+ if (S.valno != SrcValNo)
+ continue;
+ Dst.addSegment(LiveRange::Segment(S.start, S.end, DstValNo));
+ }
+}
+
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());
+
+ // We found a non-trivially-coalescable copy with IntA being the source and
+ // IntB being the dest, thus this defines a value number in IntB. If the
+ // source value number (in IntA) is defined by a commutable instruction and
+ // its other operand is coalesced to the copy dest register, see if we can
+ // transform the copy into a noop by commuting the definition. For example,
+ //
+ // A3 = op A2 B0<kill>
+ // ...
+ // B1 = A3 <- this copy
+ // ...
+ // = op A3 <- more uses
+ //
+ // ==>
+ //
+ // B2 = op B0 A2<kill>
+ // ...
+ // B1 = B2 <- now an identity copy
+ // ...
+ // = op B2 <- more uses
// 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)
unsigned UseOpIdx;
if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
return false;
- unsigned Op1, Op2, NewDstIdx;
- if (!TII->findCommutedOpIndices(DefMI, Op1, Op2))
- return false;
- if (Op1 == UseOpIdx)
- NewDstIdx = Op2;
- else if (Op2 == UseOpIdx)
- NewDstIdx = Op1;
- else
+
+ // FIXME: The code below tries to commute 'UseOpIdx' operand with some other
+ // commutable operand which is expressed by 'CommuteAnyOperandIndex'value
+ // passed to the method. That _other_ operand is chosen by
+ // the findCommutedOpIndices() method.
+ //
+ // That is obviously an area for improvement in case of instructions having
+ // more than 2 operands. For example, if some instruction has 3 commutable
+ // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3,
+ // op#2<->op#3) of commute transformation should be considered/tried here.
+ unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex;
+ if (!TII->findCommutedOpIndices(DefMI, UseOpIdx, NewDstIdx))
return false;
MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
// At this point we have decided that it is legal to do this
// transformation. Start by commuting the instruction.
MachineBasicBlock *MBB = DefMI->getParent();
- MachineInstr *NewMI = TII->commuteInstruction(DefMI);
+ MachineInstr *NewMI =
+ TII->commuteInstruction(DefMI, false, UseOpIdx, NewDstIdx);
if (!NewMI)
return false;
if (TargetRegisterInfo::isVirtualRegister(IntA.reg) &&
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);
continue;
DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI);
assert(DVNI->def == DefIdx);
- BValNo = IntB.MergeValueNumberInto(BValNo, DVNI);
+ BValNo = IntB.MergeValueNumberInto(DVNI, BValNo);
+ for (LiveInterval::SubRange &S : IntB.subranges()) {
+ VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
+ if (!SubDVNI)
+ continue;
+ VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
+ assert(SubBValNo->def == CopyIdx);
+ S.MergeValueNumberInto(SubDVNI, SubBValNo);
+ }
+
ErasedInstrs.insert(UseMI);
LIS->RemoveMachineInstrFromMaps(UseMI);
UseMI->eraseFromParent();
// Extend BValNo by merging in IntA live segments of AValNo. Val# definition
// is updated.
- VNInfo *ValNo = BValNo;
- ValNo->def = AValNo->def;
- for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
- AI != AE; ++AI) {
- if (AI->valno != AValNo) continue;
- IntB.addSegment(LiveInterval::Segment(AI->start, AI->end, ValNo));
+ BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
+ if (IntB.hasSubRanges()) {
+ if (!IntA.hasSubRanges()) {
+ LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg);
+ IntA.createSubRangeFrom(Allocator, Mask, IntA);
+ }
+ SlotIndex AIdx = CopyIdx.getRegSlot(true);
+ for (LiveInterval::SubRange &SA : IntA.subranges()) {
+ VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
+ assert(ASubValNo != nullptr);
+
+ LaneBitmask AMask = SA.LaneMask;
+ for (LiveInterval::SubRange &SB : IntB.subranges()) {
+ LaneBitmask BMask = SB.LaneMask;
+ LaneBitmask Common = BMask & AMask;
+ if (Common == 0)
+ continue;
+
+ DEBUG( dbgs() << "\t\tCopy_Merge " << PrintLaneMask(BMask)
+ << " into " << PrintLaneMask(Common) << '\n');
+ LaneBitmask BRest = BMask & ~AMask;
+ LiveInterval::SubRange *CommonRange;
+ if (BRest != 0) {
+ SB.LaneMask = BRest;
+ DEBUG(dbgs() << "\t\tReduce Lane to " << PrintLaneMask(BRest)
+ << '\n');
+ // Duplicate SubRange for newly merged common stuff.
+ CommonRange = IntB.createSubRangeFrom(Allocator, Common, SB);
+ } else {
+ // We van reuse the L SubRange.
+ SB.LaneMask = Common;
+ CommonRange = &SB;
+ }
+ LiveRange RangeCopy(SB, Allocator);
+
+ VNInfo *BSubValNo = CommonRange->getVNInfoAt(CopyIdx);
+ assert(BSubValNo->def == CopyIdx);
+ BSubValNo->def = ASubValNo->def;
+ addSegmentsWithValNo(*CommonRange, BSubValNo, SA, ASubValNo);
+ AMask &= ~BMask;
+ }
+ if (AMask != 0) {
+ DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(AMask) << '\n');
+ LiveRange *NewRange = IntB.createSubRange(Allocator, AMask);
+ VNInfo *BSubValNo = NewRange->getNextValue(CopyIdx, Allocator);
+ addSegmentsWithValNo(*NewRange, BSubValNo, SA, ASubValNo);
+ }
+ }
}
+
+ BValNo->def = AValNo->def;
+ addSegmentsWithValNo(IntB, BValNo, IntA, AValNo);
DEBUG(dbgs() << "\t\textended: " << IntB << '\n');
- IntA.removeValNo(AValNo);
+ LIS->removeVRegDefAt(IntA, AValNo->def);
+
DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n');
++numCommutes;
return true;
}
-/// If the source of a copy is defined by a trivial
-/// computation, replace the copy by rematerialize the definition.
-bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP,
+/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just
+/// defining a subregister.
+static bool definesFullReg(const MachineInstr &MI, unsigned Reg) {
+ assert(!TargetRegisterInfo::isPhysicalRegister(Reg) &&
+ "This code cannot handle physreg aliasing");
+ for (const MachineOperand &Op : MI.operands()) {
+ if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
+ continue;
+ // Return true if we define the full register or don't care about the value
+ // inside other subregisters.
+ if (Op.getSubReg() == 0 || Op.isUndef())
+ return true;
+ }
+ return false;
+}
+
+bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP,
MachineInstr *CopyMI,
bool &IsDefCopy) {
IsDefCopy = false;
return false;
if (!TII->isTriviallyReMaterializable(DefMI, AA))
return false;
+ if (!definesFullReg(*DefMI, SrcReg))
+ return false;
bool SawStore = false;
- if (!DefMI->isSafeToMove(TII, AA, SawStore))
+ if (!DefMI->isSafeToMove(AA, SawStore))
return false;
const MCInstrDesc &MCID = DefMI->getDesc();
if (MCID.getNumDefs() != 1)
TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, DefMI, *TRI);
MachineInstr *NewMI = std::prev(MII);
+ // In a situation like the following:
+ // %vreg0:subreg = instr ; DefMI, subreg = DstIdx
+ // %vreg1 = copy %vreg0:subreg ; CopyMI, SrcIdx = 0
+ // instead of widening %vreg1 to the register class of %vreg0 simply do:
+ // %vreg1 = instr
+ const TargetRegisterClass *NewRC = CP.getNewRC();
+ if (DstIdx != 0) {
+ MachineOperand &DefMO = NewMI->getOperand(0);
+ if (DefMO.getSubReg() == DstIdx) {
+ assert(SrcIdx == 0 && CP.isFlipped()
+ && "Shouldn't have SrcIdx+DstIdx at this point");
+ const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
+ const TargetRegisterClass *CommonRC =
+ TRI->getCommonSubClass(DefRC, DstRC);
+ if (CommonRC != nullptr) {
+ NewRC = CommonRC;
+ DstIdx = 0;
+ DefMO.setSubReg(0);
+ }
+ }
+ }
+
LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI);
CopyMI->eraseFromParent();
ErasedInstrs.insert(CopyMI);
for (unsigned i = NewMI->getDesc().getNumOperands(),
e = NewMI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = NewMI->getOperand(i);
- if (MO.isReg()) {
- assert(MO.isDef() && MO.isImplicit() && MO.isDead() &&
+ if (MO.isReg() && MO.isDef()) {
+ assert(MO.isImplicit() && MO.isDead() &&
TargetRegisterInfo::isPhysicalRegister(MO.getReg()));
NewMIImplDefs.push_back(MO.getReg());
}
}
if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
- const TargetRegisterClass *NewRC = CP.getNewRC();
unsigned NewIdx = NewMI->getOperand(0).getSubReg();
- if (NewIdx)
- NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
- else
- NewRC = TRI->getCommonSubClass(NewRC, DefRC);
-
- assert(NewRC && "subreg chosen for remat incompatible with instruction");
+ if (DefRC != nullptr) {
+ if (NewIdx)
+ NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
+ else
+ NewRC = TRI->getCommonSubClass(NewRC, DefRC);
+ assert(NewRC && "subreg chosen for remat incompatible with instruction");
+ }
MRI->setRegClass(DstReg, NewRC);
updateRegDefsUses(DstReg, DstReg, DstIdx);
++NumReMats;
// The source interval can become smaller because we removed a use.
- LIS->shrinkToUses(&SrcInt, &DeadDefs);
+ shrinkToUses(&SrcInt, &DeadDefs);
if (!DeadDefs.empty()) {
// If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
// to describe DstReg instead.
return true;
}
-/// ProcessImpicitDefs may leave some copies of <undef>
-/// values, it only removes local variables. When we have a copy like:
-///
-/// %vreg1 = COPY %vreg2<undef>
-///
-/// 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) {
+ // ProcessImpicitDefs may leave some copies of <undef> values, it only removes
+ // local variables. When we have a copy like:
+ //
+ // %vreg1 = COPY %vreg2<undef>
+ //
+ // We delete the copy and remove the corresponding value number from %vreg1.
+ // Any uses of that value number are marked as <undef>.
+
+ // 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()) {
+ LaneBitmask 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);
+ SlotIndex RegIndex = Idx.getRegSlot();
+ // Remove value or merge with previous one in case of a subregister def.
+ if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
+ VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
+ DstLI.MergeValueNumberInto(VNI, PrevVNI);
- VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot());
- assert(DeadVNI && "No value defined in DstInt");
- DstInt->removeValNo(DeadVNI);
+ // The affected subregister segments can be removed.
+ LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
+ for (LiveInterval::SubRange &SR : DstLI.subranges()) {
+ if ((SR.LaneMask & DstMask) == 0)
+ continue;
+
+ VNInfo *SVNI = SR.getVNInfoAt(RegIndex);
+ assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex));
+ SR.removeValNo(SVNI);
+ }
+ DstLI.removeEmptySubRanges();
+ } else
+ LIS->removeVRegDefAt(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);
+ LaneBitmask 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;
}
-/// Replace all defs and uses of SrcReg to DstReg and update the subregister
-/// number if it is not zero. If DstReg is a physical register and the existing
-/// subregister number of the def / use being updated is not zero, make sure to
-/// set it to the correct physical subregister.
void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
unsigned DstReg,
unsigned SubIdx) {
if (SubIdx && MO.isDef())
MO.setIsUndef(!Reads);
+ // A subreg use of a partially undef (super) register may be a complete
+ // undef use now and then has to be marked that way.
+ if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) {
+ if (!DstInt->hasSubRanges()) {
+ BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
+ LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg);
+ DstInt->createSubRangeFrom(Allocator, Mask, *DstInt);
+ }
+ LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubIdx);
+ bool IsUndef = true;
+ SlotIndex MIIdx = UseMI->isDebugValue()
+ ? LIS->getSlotIndexes()->getIndexBefore(UseMI)
+ : LIS->getInstructionIndex(UseMI);
+ SlotIndex UseIdx = MIIdx.getRegSlot(true);
+ for (LiveInterval::SubRange &S : DstInt->subranges()) {
+ if ((S.LaneMask & Mask) == 0)
+ continue;
+ if (S.liveAt(UseIdx)) {
+ IsUndef = false;
+ break;
+ }
+ }
+ if (IsUndef) {
+ MO.setIsUndef(true);
+ // We found out some subregister use is actually reading an undefined
+ // value. In some cases the whole vreg has become undefined at this
+ // point so we have to potentially shrink the main range if the
+ // use was ending a live segment there.
+ LiveQueryResult Q = DstInt->Query(MIIdx);
+ if (Q.valueOut() == nullptr)
+ ShrinkMainRange = true;
+ }
+ }
+
if (DstIsPhys)
MO.substPhysReg(DstReg, *TRI);
else
}
}
-/// Return true if a copy involving a physreg should be joined.
bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
- /// 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.
+ // 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 (!MRI->isReserved(CP.getDstReg())) {
DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
return false;
}
LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
- if (CP.isFlipped() && JoinVInt.containsOneValue())
+ if (JoinVInt.containsOneValue())
return true;
- DEBUG(dbgs() << "\tCannot join defs into reserved register.\n");
+ DEBUG(dbgs() << "\tCannot join complex intervals into reserved register.\n");
return false;
}
-/// Attempt to join intervals corresponding to SrcReg/DstReg,
-/// which are the src/dst of the copy instruction CopyMI. This returns true
-/// if the copy was successfully coalesced away. If it is not currently
-/// possible to coalesce this interval, but it may be possible if other
-/// things get coalesced, then it returns true by reference in 'Again'.
bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
Again = false;
}
// 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.
if (CP.getSrcReg() == CP.getDstReg()) {
LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n');
- LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(CopyMI));
+ const SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI);
+ LiveQueryResult LRQ = LI.Query(CopyIdx);
if (VNInfo *DefVNI = LRQ.valueDefined()) {
VNInfo *ReadVNI = LRQ.valueIn();
assert(ReadVNI && "No value before copy and no <undef> flag.");
assert(ReadVNI != DefVNI && "Cannot read and define the same value.");
LI.MergeValueNumberInto(DefVNI, ReadVNI);
+
+ // Process subregister liveranges.
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ LiveQueryResult SLRQ = S.Query(CopyIdx);
+ if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
+ VNInfo *SReadVNI = SLRQ.valueIn();
+ S.MergeValueNumberInto(SDefVNI, SReadVNI);
+ }
+ }
DEBUG(dbgs() << "\tMerged values: " << LI << '\n');
}
LIS->RemoveMachineInstrFromMaps(CopyMI);
});
}
+ ShrinkMask = 0;
+ ShrinkMainRange = false;
+
// Okay, attempt to join these two intervals. On failure, this returns false.
// Otherwise, if one of the intervals being joined is a physreg, this method
// always canonicalizes DstInt to be it. The output "SrcInt" will not have
updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
+ // Shrink subregister ranges if necessary.
+ if (ShrinkMask != 0) {
+ LiveInterval &LI = LIS->getInterval(CP.getDstReg());
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ if ((S.LaneMask & ShrinkMask) == 0)
+ continue;
+ DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)
+ << ")\n");
+ LIS->shrinkToUses(S, LI.reg);
+ }
+ LI.removeEmptySubRanges();
+ }
+ if (ShrinkMainRange) {
+ LiveInterval &LI = LIS->getInterval(CP.getDstReg());
+ shrinkToUses(&LI);
+ }
+
// SrcReg is guaranteed to be the register whose live interval that is
// being merged.
LIS->removeInterval(CP.getSrcReg());
// Update regalloc hint.
- TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
+ TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
DEBUG({
dbgs() << "\tSuccess: " << PrintReg(CP.getSrcReg(), TRI, CP.getSrcIdx())
return true;
}
-/// Attempt joining with a reserved physreg.
bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
+ unsigned DstReg = CP.getDstReg();
assert(CP.isPhys() && "Must be a physreg copy");
- assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register");
+ assert(MRI->isReserved(DstReg) && "Not a reserved register");
LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');
- assert(CP.isFlipped() && RHS.containsOneValue() &&
- "Invalid join with reserved register");
+ assert(RHS.containsOneValue() && "Invalid join with reserved register");
// Optimization for reserved registers like ESP. We can only merge with a
- // reserved physreg if RHS has a single value that is a copy of CP.DstReg().
+ // reserved physreg if RHS has a single value that is a copy of DstReg.
// The live range of the reserved register will look like a set of dead defs
// - we don't properly track the live range of reserved registers.
// Deny any overlapping intervals. This depends on all the reserved
// register live ranges to look like dead defs.
- for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI)
+ for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI)
if (RHS.overlaps(LIS->getRegUnit(*UI))) {
DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n');
return false;
// defs are there.
// Delete the identity copy.
- MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg);
+ MachineInstr *CopyMI;
+ if (CP.isFlipped()) {
+ CopyMI = MRI->getVRegDef(RHS.reg);
+ } else {
+ if (!MRI->hasOneNonDBGUse(RHS.reg)) {
+ DEBUG(dbgs() << "\t\tMultiple vreg uses!\n");
+ return false;
+ }
+
+ MachineInstr *DestMI = MRI->getVRegDef(RHS.reg);
+ CopyMI = &*MRI->use_instr_nodbg_begin(RHS.reg);
+ const SlotIndex CopyRegIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
+ const SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
+
+ // We checked above that there are no interfering defs of the physical
+ // register. However, for this case, where we intent to move up the def of
+ // the physical register, we also need to check for interfering uses.
+ SlotIndexes *Indexes = LIS->getSlotIndexes();
+ for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
+ SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
+ MachineInstr *MI = LIS->getInstructionFromIndex(SI);
+ if (MI->readsRegister(DstReg, TRI)) {
+ DEBUG(dbgs() << "\t\tInterference (read): " << *MI);
+ return false;
+ }
+
+ // We must also check for clobbers caused by regmasks.
+ for (const auto &MO : MI->operands()) {
+ if (MO.isRegMask() && MO.clobbersPhysReg(DstReg)) {
+ DEBUG(dbgs() << "\t\tInterference (regmask clobber): " << *MI);
+ return false;
+ }
+ }
+ }
+
+ // We're going to remove the copy which defines a physical reserved
+ // register, so remove its valno, etc.
+ DEBUG(dbgs() << "\t\tRemoving phys reg def of " << DstReg << " at "
+ << CopyRegIdx << "\n");
+
+ LIS->removePhysRegDefAt(DstReg, CopyRegIdx);
+ // Create a new dead def at the new def location.
+ for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
+ LiveRange &LR = LIS->getRegUnit(*UI);
+ LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
+ }
+ }
+
LIS->RemoveMachineInstrFromMaps(CopyMI);
CopyMI->eraseFromParent();
namespace {
/// Track information about values in a single virtual register about to be
/// joined. Objects of this class are always created in pairs - one for each
-/// side of the CoalescerPair.
+/// side of the CoalescerPair (or one for each lane of a side of the coalescer
+/// pair)
class JoinVals {
- LiveInterval &LI;
-
- // Location of this register in the final joined register.
- // Either CP.DstIdx or CP.SrcIdx.
- unsigned SubIdx;
-
- // Values that will be present in the final live range.
+ /// Live range we work on.
+ LiveRange &LR;
+ /// (Main) register we work on.
+ 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 LaneBitmask LaneMask;
+
+ /// This is true when joining sub register ranges, false when joining main
+ /// ranges.
+ const bool SubRangeJoin;
+ /// Whether the current LiveInterval tracks subregister liveness.
+ const bool TrackSubRegLiveness;
+
+ /// Values that will be present in the final live range.
SmallVectorImpl<VNInfo*> &NewVNInfo;
const CoalescerPair &CP;
SlotIndexes *Indexes;
const TargetRegisterInfo *TRI;
- // Value number assignments. Maps value numbers in LI to entries in NewVNInfo.
- // This is suitable for passing to LiveInterval::join().
+ /// Value number assignments. Maps value numbers in LI to entries in
+ /// NewVNInfo. This is suitable for passing to LiveInterval::join().
SmallVector<int, 8> Assignments;
- // Conflict resolution for overlapping values.
+ /// Conflict resolution for overlapping values.
enum ConflictResolution {
- // No overlap, simply keep this value.
+ /// No overlap, simply keep this value.
CR_Keep,
- // Merge this value into OtherVNI and erase the defining instruction.
- // Used for IMPLICIT_DEF, coalescable copies, and copies from external
- // values.
+ /// Merge this value into OtherVNI and erase the defining instruction.
+ /// Used for IMPLICIT_DEF, coalescable copies, and copies from external
+ /// values.
CR_Erase,
- // Merge this value into OtherVNI but keep the defining instruction.
- // This is for the special case where OtherVNI is defined by the same
- // instruction.
+ /// Merge this value into OtherVNI but keep the defining instruction.
+ /// This is for the special case where OtherVNI is defined by the same
+ /// instruction.
CR_Merge,
- // Keep this value, and have it replace OtherVNI where possible. This
- // complicates value mapping since OtherVNI maps to two different values
- // before and after this def.
- // Used when clobbering undefined or dead lanes.
+ /// Keep this value, and have it replace OtherVNI where possible. This
+ /// complicates value mapping since OtherVNI maps to two different values
+ /// before and after this def.
+ /// Used when clobbering undefined or dead lanes.
CR_Replace,
- // Unresolved conflict. Visit later when all values have been mapped.
+ /// Unresolved conflict. Visit later when all values have been mapped.
CR_Unresolved,
- // Unresolvable conflict. Abort the join.
+ /// Unresolvable conflict. Abort the join.
CR_Impossible
};
- // Per-value info for LI. The lane bit masks are all relative to the final
- // joined register, so they can be compared directly between SrcReg and
- // DstReg.
+ /// Per-value info for LI. The lane bit masks are all relative to the final
+ /// joined register, so they can be compared directly between SrcReg and
+ /// DstReg.
struct Val {
ConflictResolution Resolution;
- // Lanes written by this def, 0 for unanalyzed values.
- unsigned WriteLanes;
+ /// Lanes written by this def, 0 for unanalyzed values.
+ LaneBitmask WriteLanes;
- // Lanes with defined values in this register. Other lanes are undef and
- // safe to clobber.
- unsigned ValidLanes;
+ /// Lanes with defined values in this register. Other lanes are undef and
+ /// safe to clobber.
+ LaneBitmask ValidLanes;
- // Value in LI being redefined by this def.
+ /// Value in LI being redefined by this def.
VNInfo *RedefVNI;
- // Value in the other live range that overlaps this def, if any.
+ /// Value in the other live range that overlaps this def, if any.
VNInfo *OtherVNI;
- // Is this value an IMPLICIT_DEF that can be erased?
- //
- // IMPLICIT_DEF values should only exist at the end of a basic block that
- // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
- // safely erased if they are overlapping a live value in the other live
- // interval.
- //
- // Weird control flow graphs and incomplete PHI handling in
- // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
- // longer live ranges. Such IMPLICIT_DEF values should be treated like
- // normal values.
+ /// Is this value an IMPLICIT_DEF that can be erased?
+ ///
+ /// IMPLICIT_DEF values should only exist at the end of a basic block that
+ /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
+ /// safely erased if they are overlapping a live value in the other live
+ /// interval.
+ ///
+ /// Weird control flow graphs and incomplete PHI handling in
+ /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
+ /// longer live ranges. Such IMPLICIT_DEF values should be treated like
+ /// normal values.
bool ErasableImplicitDef;
- // True when the live range of this value will be pruned because of an
- // overlapping CR_Replace value in the other live range.
+ /// 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.
+ /// True once Pruned above has been computed.
bool PrunedComputed;
Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0),
bool isAnalyzed() const { return WriteLanes != 0; }
};
- // One entry per value number in LI.
+ /// One entry per value number in LI.
SmallVector<Val, 8> Vals;
- unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef);
- VNInfo *stripCopies(VNInfo *VNI);
+ /// 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.
+ LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
+
+ /// Find the ultimate value that VNI was copied from.
+ std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
+
+ bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
+
+ /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
+ /// Return a conflict resolution when possible, but leave the hard cases as
+ /// CR_Unresolved.
+ /// Recursively calls computeAssignment() on this and Other, guaranteeing that
+ /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
+ /// The recursion always goes upwards in the dominator tree, making loops
+ /// impossible.
ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
+
+ /// Compute the value assignment for ValNo in RI.
+ /// This may be called recursively by analyzeValue(), but never for a ValNo on
+ /// the stack.
void computeAssignment(unsigned ValNo, JoinVals &Other);
- bool taintExtent(unsigned, unsigned, JoinVals&,
- SmallVectorImpl<std::pair<SlotIndex, unsigned> >&);
- bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned);
+
+ /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute
+ /// the extent of the tainted lanes in the block.
+ ///
+ /// Multiple values in Other.LR 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 taintExtent(unsigned, LaneBitmask, JoinVals&,
+ SmallVectorImpl<std::pair<SlotIndex, LaneBitmask> >&);
+
+ /// Return true if MI uses any of the given Lanes from Reg.
+ /// This does not include partial redefinitions of Reg.
+ bool usesLanes(const MachineInstr *MI, unsigned, unsigned, LaneBitmask) const;
+
+ /// Determine if ValNo is a copy of a value number in LR or Other.LR 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 isPrunedValue(unsigned ValNo, JoinVals &Other);
public:
- JoinVals(LiveInterval &li, unsigned subIdx,
- SmallVectorImpl<VNInfo*> &newVNInfo,
- const CoalescerPair &cp,
- LiveIntervals *lis,
- const TargetRegisterInfo *tri)
- : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis),
- Indexes(LIS->getSlotIndexes()), TRI(tri),
- Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums())
+ JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, LaneBitmask LaneMask,
+ SmallVectorImpl<VNInfo*> &newVNInfo, const CoalescerPair &cp,
+ LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
+ bool TrackSubRegLiveness)
+ : 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())
{}
- /// Analyze defs in LI and compute a value mapping in NewVNInfo.
+ /// Analyze defs in LR and compute a value mapping in NewVNInfo.
/// Returns false if any conflicts were impossible to resolve.
bool mapValues(JoinVals &Other);
/// Returns false if any conflicts were impossible to resolve.
bool resolveConflicts(JoinVals &Other);
- /// Prune the live range of values in Other.LI where they would conflict with
- /// CR_Replace values in LI. Collect end points for restoring the live range
+ /// Prune the live range of values in Other.LR where they would conflict with
+ /// CR_Replace values in LR. Collect end points for restoring the live range
/// after joining.
- void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints);
+ void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
+ bool changeInstrs);
+
+ /// Removes subranges starting at copies that get removed. This sometimes
+ /// happens when undefined subranges are copied around. These ranges contain
+ /// no useful information and can be removed.
+ void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
/// Erase any machine instructions that have been coalesced away.
/// Add erased instructions to ErasedInstrs.
void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
SmallVectorImpl<unsigned> &ShrinkRegs);
+ /// Remove liverange defs at places where implicit defs will be removed.
+ void removeImplicitDefs();
+
/// Get the value assignments suitable for passing to LiveInterval::join.
const int *getAssignments() const { return Assignments.data(); }
};
} // end anonymous namespace
-/// 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 L = 0;
- for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) {
- if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef())
+LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
+ const {
+ LaneBitmask L = 0;
+ for (const MachineOperand &MO : DefMI->operands()) {
+ if (!MO.isReg() || MO.getReg() != Reg || !MO.isDef())
continue;
L |= TRI->getSubRegIndexLaneMask(
- TRI->composeSubRegIndices(SubIdx, MO->getSubReg()));
- if (MO->readsReg())
+ TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
+ if (MO.readsReg())
Redef = true;
}
return L;
}
-/// 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.
+ LaneBitmask 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].
-/// Return a conflict resolution when possible, but leave the hard cases as
-/// CR_Unresolved.
-/// Recursively calls computeAssignment() on this and Other, guaranteeing that
-/// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
-/// The recursion always goes upwards in the dominator tree, making loops
-/// impossible.
JoinVals::ConflictResolution
JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
Val &V = Vals[ValNo];
assert(!V.isAnalyzed() && "Value has already been analyzed!");
- VNInfo *VNI = LI.getValNumInfo(ValNo);
+ VNInfo *VNI = LR.getValNumInfo(ValNo);
if (VNI->isUnused()) {
V.WriteLanes = ~0u;
return CR_Keep;
const MachineInstr *DefMI = nullptr;
if (VNI->isPHIDef()) {
// Conservatively assume that all lanes in a PHI are valid.
- V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx);
+ LaneBitmask Lanes = SubRangeJoin ? 1 : TRI->getSubRegIndexLaneMask(SubIdx);
+ V.ValidLanes = V.WriteLanes = Lanes;
} else {
DefMI = Indexes->getInstructionFromIndex(VNI->def);
- bool Redef = false;
- V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
-
- // If this is a read-modify-write instruction, there may be more valid
- // lanes than the ones written by this instruction.
- // This only covers partial redef operands. DefMI may have normal use
- // operands reading the register. They don't contribute valid lanes.
- //
- // This adds ssub1 to the set of valid lanes in %src:
- //
- // %src:ssub1<def> = FOO
- //
- // This leaves only ssub1 valid, making any other lanes undef:
- //
- // %src:ssub1<def,read-undef> = FOO %src:ssub2
- //
- // The <read-undef> flag on the def operand means that old lane values are
- // not important.
- if (Redef) {
- V.RedefVNI = LI.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(DefMI != nullptr);
+ if (SubRangeJoin) {
+ // We don't care about the lanes when joining subregister ranges.
+ V.WriteLanes = V.ValidLanes = 1;
+ if (DefMI->isImplicitDef()) {
+ V.ValidLanes = 0;
+ V.ErasableImplicitDef = true;
+ }
+ } else {
+ bool Redef = false;
+ V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
+
+ // If this is a read-modify-write instruction, there may be more valid
+ // lanes than the ones written by this instruction.
+ // This only covers partial redef operands. DefMI may have normal use
+ // operands reading the register. They don't contribute valid lanes.
+ //
+ // This adds ssub1 to the set of valid lanes in %src:
+ //
+ // %src:ssub1<def> = FOO
+ //
+ // This leaves only ssub1 valid, making any other lanes undef:
+ //
+ // %src:ssub1<def,read-undef> = FOO %src:ssub2
+ //
+ // The <read-undef> flag on the def operand means that old lane values are
+ // not important.
+ if (Redef) {
+ V.RedefVNI = LR.Query(VNI->def).valueIn();
+ 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.
- if (DefMI->isImplicitDef()) {
- // We normally expect IMPLICIT_DEF values to be live only until the end
- // of their block. If the value is really live longer and gets pruned in
- // another block, this flag is cleared again.
- V.ErasableImplicitDef = true;
- V.ValidLanes &= ~V.WriteLanes;
+ // An IMPLICIT_DEF writes undef values.
+ if (DefMI->isImplicitDef()) {
+ // We normally expect IMPLICIT_DEF values to be live only until the end
+ // of their block. If the value is really live longer and gets pruned in
+ // another block, this flag is cleared again.
+ V.ErasableImplicitDef = true;
+ V.ValidLanes &= ~V.WriteLanes;
+ }
}
}
// Find the value in Other that overlaps VNI->def, if any.
- LiveQueryResult OtherLRQ = Other.LI.Query(VNI->def);
+ LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);
// It is possible that both values are defined by the same instruction, or
// the values are PHIs defined in the same block. When that happens, the two
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() &&
- stripCopies(VNI) == stripCopies(V.OtherVNI))
+ 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
// 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.
+ // Otherwise Other.RI wouldn't be live here.
if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0)
return CR_Impossible;
return CR_Unresolved;
}
-/// Compute the value assignment for ValNo in LI.
-/// This may be called recursively by analyzeValue(), but never for a ValNo on
-/// the stack.
void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
Val &V = Vals[ValNo];
if (V.isAnalyzed()) {
assert(V.OtherVNI && "OtherVNI not assigned, can't merge.");
assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion");
Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
- DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@'
- << LI.getValNumInfo(ValNo)->def << " into "
- << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@'
+ DEBUG(dbgs() << "\t\tmerge " << PrintReg(Reg) << ':' << ValNo << '@'
+ << LR.getValNumInfo(ValNo)->def << " into "
+ << PrintReg(Other.Reg) << ':' << V.OtherVNI->id << '@'
<< V.OtherVNI->def << " --> @"
<< NewVNInfo[Assignments[ValNo]]->def << '\n');
break;
case CR_Replace:
- case CR_Unresolved:
+ 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;
+ Val &OtherV = Other.Vals[V.OtherVNI->id];
+ // We cannot erase an IMPLICIT_DEF if we don't have valid values for all
+ // its lanes.
+ if ((OtherV.WriteLanes & ~V.ValidLanes) != 0 && TrackSubRegLiveness)
+ OtherV.ErasableImplicitDef = false;
+ OtherV.Pruned = true;
+ }
// Fall through.
default:
// This value number needs to go in the final joined live range.
Assignments[ValNo] = NewVNInfo.size();
- NewVNInfo.push_back(LI.getValNumInfo(ValNo));
+ NewVNInfo.push_back(LR.getValNumInfo(ValNo));
break;
}
}
bool JoinVals::mapValues(JoinVals &Other) {
- for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
+ for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
computeAssignment(i, Other);
if (Vals[i].Resolution == CR_Impossible) {
- DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i
- << '@' << LI.getValNumInfo(i)->def << '\n');
+ DEBUG(dbgs() << "\t\tinterference at " << PrintReg(Reg) << ':' << i
+ << '@' << LR.getValNumInfo(i)->def << '\n');
return false;
}
}
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);
+taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
+ SmallVectorImpl<std::pair<SlotIndex, LaneBitmask> > &TaintExtent) {
+ VNInfo *VNI = LR.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?");
+ // Scan Other.LR from VNI.def to MBBEnd.
+ LiveInterval::iterator OtherI = Other.LR.find(VNI->def);
+ assert(OtherI != Other.LR.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) << ':'
+ DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.Reg) << ':'
<< OtherI->valno->id << '@' << OtherI->start << '\n');
return false;
}
- DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':'
+ DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.Reg) << ':'
<< OtherI->valno->id << '@' << OtherI->start
<< " to " << End << '\n');
// A dead def is not a problem.
TaintExtent.push_back(std::make_pair(End, TaintedLanes));
// Check for another def in the MBB.
- if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd)
+ if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
break;
// Lanes written by the new def are no longer tainted.
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) {
+bool JoinVals::usesLanes(const MachineInstr *MI, unsigned Reg, unsigned SubIdx,
+ LaneBitmask Lanes) const {
if (MI->isDebugValue())
return false;
- for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
- if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg)
+ for (const MachineOperand &MO : MI->operands()) {
+ if (!MO.isReg() || MO.isDef() || MO.getReg() != Reg)
continue;
- if (!MO->readsReg())
+ if (!MO.readsReg())
continue;
if (Lanes & TRI->getSubRegIndexLaneMask(
- TRI->composeSubRegIndices(SubIdx, MO->getSubReg())))
+ TRI->composeSubRegIndices(SubIdx, MO.getSubReg())))
return true;
}
return false;
}
bool JoinVals::resolveConflicts(JoinVals &Other) {
- for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
+ for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
Val &V = Vals[i];
assert (V.Resolution != CR_Impossible && "Unresolvable conflict");
if (V.Resolution != CR_Unresolved)
continue;
- DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i
- << '@' << LI.getValNumInfo(i)->def << '\n');
+ DEBUG(dbgs() << "\t\tconflict at " << PrintReg(Reg) << ':' << i
+ << '@' << LR.getValNumInfo(i)->def << '\n');
+ if (SubRangeJoin)
+ return false;
+
++NumLaneConflicts;
assert(V.OtherVNI && "Inconsistent conflict resolution.");
- VNInfo *VNI = LI.getValNumInfo(i);
+ VNInfo *VNI = LR.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;
+ LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
+ SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent;
if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
// Tainted lanes would extend beyond the basic block.
return false;
unsigned TaintNum = 0;
for(;;) {
assert(MI != MBB->end() && "Bad LastMI");
- if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) {
+ if (usesLanes(MI, Other.Reg, Other.SubIdx, TaintedLanes)) {
DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI);
return false;
}
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)
}
void JoinVals::pruneValues(JoinVals &Other,
- SmallVectorImpl<SlotIndex> &EndPoints) {
- for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
- SlotIndex Def = LI.getValNumInfo(i)->def;
+ SmallVectorImpl<SlotIndex> &EndPoints,
+ bool changeInstrs) {
+ for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
+ SlotIndex Def = LR.getValNumInfo(i)->def;
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);
+ // This value takes precedence over the value in Other.LR.
+ LIS->pruneValue(Other.LR, 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
bool EraseImpDef = OtherV.ErasableImplicitDef &&
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);
+ if (changeInstrs) {
+ // 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 (MachineOperand &MO :
+ Indexes->getInstructionFromIndex(Def)->operands()) {
+ if (MO.isReg() && MO.isDef() && MO.getReg() == 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');
+ DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.Reg) << " at " << Def
+ << ": " << Other.LR << '\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.
+ // This value is ultimately a copy of a pruned value in LR or Other.LR.
// 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');
+ LIS->pruneValue(LR, Def, &EndPoints);
+ DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(Reg) << " at "
+ << Def << ": " << LR << '\n');
}
break;
case CR_Unresolved:
}
}
+void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask)
+{
+ // Look for values being erased.
+ bool DidPrune = false;
+ for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
+ if (Vals[i].Resolution != CR_Erase)
+ continue;
+
+ // Check subranges at the point where the copy will be removed.
+ SlotIndex Def = LR.getValNumInfo(i)->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 " << PrintLaneMask(S.LaneMask)
+ << " at " << Def << "\n");
+ LIS->pruneValue(S, Def, nullptr);
+ DidPrune = true;
+ // Mark value number as unused.
+ ValueOut->markUnused();
+ continue;
+ }
+ // If a subrange ends at the copy, then a value was copied but only
+ // partially used later. Shrink the subregister range appropriately.
+ if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
+ DEBUG(dbgs() << "\t\tDead uses at sublane " << PrintLaneMask(S.LaneMask)
+ << " at " << Def << "\n");
+ ShrinkMask |= S.LaneMask;
+ }
+ }
+ }
+ if (DidPrune)
+ LI.removeEmptySubRanges();
+}
+
+void JoinVals::removeImplicitDefs() {
+ for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
+ Val &V = Vals[i];
+ if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
+ continue;
+
+ VNInfo *VNI = LR.getValNumInfo(i);
+ VNI->markUnused();
+ LR.removeValNo(VNI);
+ }
+}
+
void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
SmallVectorImpl<unsigned> &ShrinkRegs) {
- for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) {
+ for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
// Get the def location before markUnused() below invalidates it.
- SlotIndex Def = LI.getValNumInfo(i)->def;
+ SlotIndex Def = LR.getValNumInfo(i)->def;
switch (Vals[i].Resolution) {
- case CR_Keep:
+ 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].ErasableImplicitDef || !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');
+ // Remove value number i from LR.
+ VNInfo *VNI = LR.getValNumInfo(i);
+ LR.removeValNo(VNI);
+ // Note that this VNInfo is reused and still referenced in NewVNInfo,
+ // make it appear like an unused value number.
+ VNI->markUnused();
+ DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n');
// FALL THROUGH.
+ }
case CR_Erase: {
MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
}
}
+bool RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
+ LaneBitmask LaneMask,
+ const CoalescerPair &CP) {
+ SmallVector<VNInfo*, 16> NewVNInfo;
+ JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
+ NewVNInfo, CP, LIS, TRI, true, true);
+ JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
+ NewVNInfo, CP, LIS, TRI, true, true);
+
+ // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
+ // We should be able to resolve all conflicts here as we could successfully do
+ // it on the mainrange already. There is however a problem when multiple
+ // ranges get mapped to the "overflow" lane mask bit which creates unexpected
+ // interferences.
+ if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
+ DEBUG(dbgs() << "*** Couldn't join subrange!\n");
+ return false;
+ }
+ if (!LHSVals.resolveConflicts(RHSVals) ||
+ !RHSVals.resolveConflicts(LHSVals)) {
+ DEBUG(dbgs() << "*** Couldn't join subrange!\n");
+ return false;
+ }
+
+ // The merging algorithm in LiveInterval::join() can't handle conflicting
+ // value mappings, so we need to remove any live ranges that overlap a
+ // CR_Replace resolution. Collect a set of end points that can be used to
+ // restore the live range after joining.
+ SmallVector<SlotIndex, 8> EndPoints;
+ LHSVals.pruneValues(RHSVals, EndPoints, false);
+ RHSVals.pruneValues(LHSVals, EndPoints, false);
+
+ LHSVals.removeImplicitDefs();
+ RHSVals.removeImplicitDefs();
+
+ LRange.verify();
+ RRange.verify();
+
+ // Join RRange into LHS.
+ LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
+ NewVNInfo);
+
+ DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n");
+ if (EndPoints.empty())
+ return true;
+
+ // Recompute the parts of the live range we had to remove because of
+ // CR_Replace conflicts.
+ DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size()
+ << " points: " << LRange << '\n');
+ LIS->extendToIndices(LRange, EndPoints);
+ return true;
+}
+
+bool RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
+ const LiveRange &ToMerge,
+ LaneBitmask LaneMask,
+ CoalescerPair &CP) {
+ BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
+ for (LiveInterval::SubRange &R : LI.subranges()) {
+ LaneBitmask RMask = R.LaneMask;
+ // LaneMask of subregisters common to subrange R and ToMerge.
+ LaneBitmask Common = RMask & LaneMask;
+ // There is nothing to do without common subregs.
+ if (Common == 0)
+ continue;
+
+ DEBUG(dbgs() << "\t\tCopy+Merge " << PrintLaneMask(RMask) << " into "
+ << PrintLaneMask(Common) << '\n');
+ // LaneMask of subregisters contained in the R range but not in ToMerge,
+ // they have to split into their own subrange.
+ LaneBitmask LRest = RMask & ~LaneMask;
+ LiveInterval::SubRange *CommonRange;
+ if (LRest != 0) {
+ R.LaneMask = LRest;
+ DEBUG(dbgs() << "\t\tReduce Lane to " << PrintLaneMask(LRest) << '\n');
+ // Duplicate SubRange for newly merged common stuff.
+ CommonRange = LI.createSubRangeFrom(Allocator, Common, R);
+ } else {
+ // Reuse the existing range.
+ R.LaneMask = Common;
+ CommonRange = &R;
+ }
+ LiveRange RangeCopy(ToMerge, Allocator);
+ if (!joinSubRegRanges(*CommonRange, RangeCopy, Common, CP))
+ return false;
+ LaneMask &= ~RMask;
+ }
+
+ if (LaneMask != 0) {
+ DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(LaneMask) << '\n');
+ LI.createSubRangeFrom(Allocator, LaneMask, ToMerge);
+ }
+ return true;
+}
+
bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
SmallVector<VNInfo*, 16> NewVNInfo;
LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
- JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI);
- JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI);
+ bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
+ 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
return false;
// 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()) {
+ LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
+ : TRI->getSubRegIndexLaneMask(DstIdx);
+ // LHS must support subregs or we wouldn't be in this codepath.
+ assert(Mask != 0);
+ LHS.createSubRangeFrom(Allocator, Mask, LHS);
+ } else if (DstIdx != 0) {
+ // Transform LHS lanemasks to new register class if necessary.
+ for (LiveInterval::SubRange &R : LHS.subranges()) {
+ LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
+ R.LaneMask = Mask;
+ }
+ }
+ DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg())
+ << ' ' << LHS << '\n');
+
+ // Determine lanemasks of RHS in the coalesced register and merge subranges.
+ unsigned SrcIdx = CP.getSrcIdx();
+ bool Abort = false;
+ if (!RHS.hasSubRanges()) {
+ LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
+ : TRI->getSubRegIndexLaneMask(SrcIdx);
+ if (!mergeSubRangeInto(LHS, RHS, Mask, CP))
+ Abort = true;
+ } else {
+ // Pair up subranges and merge.
+ for (LiveInterval::SubRange &R : RHS.subranges()) {
+ LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
+ if (!mergeSubRangeInto(LHS, R, Mask, CP)) {
+ Abort = true;
+ break;
+ }
+ }
+ }
+ if (Abort) {
+ // This shouldn't have happened :-(
+ // However we are aware of at least one existing problem where we
+ // can't merge subranges when multiple ranges end up in the
+ // "overflow bit" 32. As a workaround we drop all subregister ranges
+ // which means we loose some precision but are back to a well defined
+ // state.
+ assert(TargetRegisterInfo::isImpreciseLaneMask(
+ CP.getNewRC()->getLaneMask())
+ && "SubRange merge should only fail when merging into bit 32.");
+ DEBUG(dbgs() << "\tSubrange join aborted!\n");
+ LHS.clearSubRanges();
+ RHS.clearSubRanges();
+ } else {
+ DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
+
+ LHSVals.pruneSubRegValues(LHS, ShrinkMask);
+ RHSVals.pruneSubRegValues(LHS, ShrinkMask);
+ }
+ }
// The merging algorithm in LiveInterval::join() can't handle conflicting
// value mappings, so we need to remove any live ranges that overlap a
// CR_Replace resolution. Collect a set of end points that can be used to
// restore the live range after joining.
SmallVector<SlotIndex, 8> EndPoints;
- LHSVals.pruneValues(RHSVals, EndPoints);
- RHSVals.pruneValues(LHSVals, EndPoints);
+ LHSVals.pruneValues(RHSVals, EndPoints, true);
+ RHSVals.pruneValues(LHSVals, EndPoints, true);
// Erase COPY and IMPLICIT_DEF instructions. This may cause some external
// registers to require trimming.
LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
while (!ShrinkRegs.empty())
- LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
+ shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
// Join RHS into LHS.
LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
MRI->clearKillFlags(LHS.reg);
MRI->clearKillFlags(RHS.reg);
- if (EndPoints.empty())
- return true;
+ if (!EndPoints.empty()) {
+ // Recompute the parts of the live range we had to remove because of
+ // CR_Replace conflicts.
+ DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size()
+ << " points: " << LHS << '\n');
+ LIS->extendToIndices((LiveRange&)LHS, EndPoints);
+ }
- // Recompute the parts of the live range we had to remove because of
- // CR_Replace conflicts.
- DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size()
- << " points: " << LHS << '\n');
- LIS->extendToIndices(LHS, EndPoints);
return true;
}
-/// Attempt to join these two intervals. On failure, this returns false.
bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
}
namespace {
-// Information concerning MBB coalescing priority.
+/// Information concerning MBB coalescing priority.
struct MBBPriorityInfo {
MachineBasicBlock *MBB;
unsigned Depth;
};
}
-// C-style comparator that sorts first based on the loop depth of the basic
-// block (the unsigned), and then on the MBB number.
-//
-// EnableGlobalCopies assumes that the primary sort key is loop depth.
+/// C-style comparator that sorts first based on the loop depth of the basic
+/// block (the unsigned), and then on the MBB number.
+///
+/// EnableGlobalCopies assumes that the primary sort key is loop depth.
static int compareMBBPriority(const MBBPriorityInfo *LHS,
const MBBPriorityInfo *RHS) {
// Deeper loops first
|| LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));
}
-// Try joining WorkList copies starting from index From.
-// Null out any successful joins.
bool RegisterCoalescer::
copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) {
bool Progress = false;
return Progress;
}
+/// Check if DstReg is a terminal node.
+/// I.e., it does not have any affinity other than \p Copy.
+static bool isTerminalReg(unsigned DstReg, const MachineInstr &Copy,
+ const MachineRegisterInfo *MRI) {
+ assert(Copy.isCopyLike());
+ // Check if the destination of this copy as any other affinity.
+ for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
+ if (&MI != &Copy && MI.isCopyLike())
+ return false;
+ return true;
+}
+
+bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
+ assert(Copy.isCopyLike());
+ if (!UseTerminalRule)
+ return false;
+ unsigned DstReg, DstSubReg, SrcReg, SrcSubReg;
+ isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg);
+ // Check if the destination of this copy has any other affinity.
+ if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
+ // If SrcReg is a physical register, the copy won't be coalesced.
+ // Ignoring it may have other side effect (like missing
+ // rematerialization). So keep it.
+ TargetRegisterInfo::isPhysicalRegister(SrcReg) ||
+ !isTerminalReg(DstReg, Copy, MRI))
+ return false;
+
+ // DstReg is a terminal node. Check if it interferes with any other
+ // copy involving SrcReg.
+ const MachineBasicBlock *OrigBB = Copy.getParent();
+ const LiveInterval &DstLI = LIS->getInterval(DstReg);
+ for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
+ // Technically we should check if the weight of the new copy is
+ // interesting compared to the other one and update the weight
+ // of the copies accordingly. However, this would only work if
+ // we would gather all the copies first then coalesce, whereas
+ // right now we interleave both actions.
+ // For now, just consider the copies that are in the same block.
+ if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)
+ continue;
+ unsigned OtherReg, OtherSubReg, OtherSrcReg, OtherSrcSubReg;
+ isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
+ OtherSubReg);
+ if (OtherReg == SrcReg)
+ OtherReg = OtherSrcReg;
+ // Check if OtherReg is a non-terminal.
+ if (TargetRegisterInfo::isPhysicalRegister(OtherReg) ||
+ isTerminalReg(OtherReg, MI, MRI))
+ continue;
+ // Check that OtherReg interfere with DstReg.
+ if (LIS->getInterval(OtherReg).overlaps(DstLI)) {
+ DEBUG(dbgs() << "Apply terminal rule for: " << PrintReg(DstReg) << '\n');
+ return true;
+ }
+ }
+ return false;
+}
+
void
RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
DEBUG(dbgs() << MBB->getName() << ":\n");
// yet, it might invalidate the iterator.
const unsigned PrevSize = WorkList.size();
if (JoinGlobalCopies) {
+ SmallVector<MachineInstr*, 2> LocalTerminals;
+ SmallVector<MachineInstr*, 2> GlobalTerminals;
// Coalesce copies bottom-up to coalesce local defs before local uses. They
// are not inherently easier to resolve, but slightly preferable until we
// have local live range splitting. In particular this is required by
MII != E; ++MII) {
if (!MII->isCopyLike())
continue;
- if (isLocalCopy(&(*MII), LIS))
- LocalWorkList.push_back(&(*MII));
- else
- WorkList.push_back(&(*MII));
+ bool ApplyTerminalRule = applyTerminalRule(*MII);
+ if (isLocalCopy(&(*MII), LIS)) {
+ if (ApplyTerminalRule)
+ LocalTerminals.push_back(&(*MII));
+ else
+ LocalWorkList.push_back(&(*MII));
+ } else {
+ if (ApplyTerminalRule)
+ GlobalTerminals.push_back(&(*MII));
+ else
+ WorkList.push_back(&(*MII));
+ }
}
+ // Append the copies evicted by the terminal rule at the end of the list.
+ LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());
+ WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());
}
else {
+ SmallVector<MachineInstr*, 2> Terminals;
for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
MII != E; ++MII)
- if (MII->isCopyLike())
- WorkList.push_back(MII);
+ if (MII->isCopyLike()) {
+ if (applyTerminalRule(*MII))
+ Terminals.push_back(&(*MII));
+ else
+ WorkList.push_back(MII);
+ }
+ // Append the copies evicted by the terminal rule at the end of the list.
+ WorkList.append(Terminals.begin(), Terminals.end());
}
// Try coalescing the collected copies immediately, and remove the nulls.
// This prevents the WorkList from getting too large since most copies are
std::vector<MBBPriorityInfo> MBBs;
MBBs.reserve(MF->size());
for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){
- MachineBasicBlock *MBB = I;
+ MachineBasicBlock *MBB = &*I;
MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB),
JoinSplitEdges && isSplitEdge(MBB)));
}
MF = &fn;
MRI = &fn.getRegInfo();
TM = &fn.getTarget();
- TRI = TM->getSubtargetImpl()->getRegisterInfo();
- TII = TM->getSubtargetImpl()->getInstrInfo();
+ const TargetSubtargetInfo &STI = fn.getSubtarget();
+ TRI = STI.getRegisterInfo();
+ TII = STI.getInstrInfo();
LIS = &getAnalysis<LiveIntervals>();
- AA = &getAnalysis<AliasAnalysis>();
+ AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Loops = &getAnalysis<MachineLoopInfo>();
-
- const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>();
if (EnableGlobalCopies == cl::BOU_UNSET)
- JoinGlobalCopies = ST.useMachineScheduler();
+ JoinGlobalCopies = STI.enableJoinGlobalCopies();
else
JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);
unsigned Reg = InflateRegs[i];
if (MRI->reg_nodbg_empty(Reg))
continue;
- if (MRI->recomputeRegClass(Reg, *TM)) {
+ if (MRI->recomputeRegClass(Reg)) {
DEBUG(dbgs() << PrintReg(Reg) << " inflated to "
<< TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n');
+ LiveInterval &LI = LIS->getInterval(Reg);
+ LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
+ if (MaxMask == 0) {
+ // If the inflated register class does not support subregisters anymore
+ // remove the subranges.
+ LI.clearSubRanges();
+ } else {
+#ifndef NDEBUG
+ // If subranges are still supported, then the same subregs should still
+ // be supported.
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ assert ((S.LaneMask & ~MaxMask) == 0);
+ }
+#endif
+ }
++NumInflated;
}
}
return true;
}
-/// Implement the dump method.
void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
LIS->print(O, m);
}
projects / oota-llvm.git / blobdiff