66#define DEBUG_TYPE "regalloc"
68STATISTIC(numJoins,
"Number of interval joins performed");
69STATISTIC(numCrossRCs,
"Number of cross class joins performed");
70STATISTIC(numCommutes,
"Number of instruction commuting performed");
72STATISTIC(NumReMats,
"Number of instructions re-materialized");
73STATISTIC(NumInflated,
"Number of register classes inflated");
74STATISTIC(NumLaneConflicts,
"Number of dead lane conflicts tested");
75STATISTIC(NumLaneResolves,
"Number of dead lane conflicts resolved");
76STATISTIC(NumShrinkToUses,
"Number of shrinkToUses called");
83 const CodeGenOptions &Opts;
101 DenseMap<unsigned, PHIValPos> PHIValToPos;
105 DenseMap<Register, SmallVector<unsigned, 2>> RegToPHIIdx;
110 using DbgValueLoc = std::pair<SlotIndex, MachineInstr *>;
111 DenseMap<Register, std::vector<DbgValueLoc>> DbgVRegToValues;
115 LaneBitmask ShrinkMask;
123 bool ShrinkMainRange =
false;
127 bool JoinGlobalCopies =
false;
131 bool JoinSplitEdges =
false;
134 SmallVector<MachineInstr *, 8> WorkList;
135 SmallVector<MachineInstr *, 8> LocalWorkList;
139 SmallPtrSet<MachineInstr *, 8> ErasedInstrs;
142 SmallVector<MachineInstr *, 8> DeadDefs;
150 DenseSet<Register> ToBeUpdated;
154 DenseMap<Register, unsigned long> LargeLIVisitCounter;
157 void eliminateDeadDefs(LiveRangeEdit *Edit =
nullptr);
160 void LRE_WillEraseInstruction(MachineInstr *
MI)
override;
163 void coalesceLocals();
166 void joinAllIntervals();
170 void copyCoalesceInMBB(MachineBasicBlock *
MBB);
181 void lateLiveIntervalUpdate();
186 bool copyValueUndefInPredecessors(
LiveRange &S,
const MachineBasicBlock *
MBB,
187 LiveQueryResult SLRQ);
191 void setUndefOnPrunedSubRegUses(LiveInterval &LI,
Register Reg,
192 LaneBitmask PrunedLanes);
199 enum class JoinResult { Joined, Deferred, Rejected };
203 JoinResult joinCopy(MachineInstr *CopyMI,
204 SmallPtrSetImpl<MachineInstr *> &CurrentErasedInstrs);
210 JoinResult joinIntervals(CoalescerPair &CP);
213 JoinResult joinVirtRegs(CoalescerPair &CP);
218 bool isHighCostLiveInterval(LiveInterval &LI);
221 bool joinReservedPhysReg(CoalescerPair &CP);
228 void mergeSubRangeInto(LiveInterval &LI,
const LiveRange &ToMerge,
229 LaneBitmask LaneMask, CoalescerPair &CP,
235 LaneBitmask LaneMask,
const CoalescerPair &CP);
241 bool adjustCopiesBackFrom(
const CoalescerPair &CP, MachineInstr *CopyMI);
245 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
246 VNInfo *AValNo, VNInfo *BValNo);
256 std::pair<bool, bool> removeCopyByCommutingDef(
const CoalescerPair &CP,
257 MachineInstr *CopyMI);
260 bool removePartialRedundancy(
const CoalescerPair &CP, MachineInstr &CopyMI);
264 bool reMaterializeDef(
const CoalescerPair &CP, MachineInstr *CopyMI,
268 bool canJoinPhys(
const CoalescerPair &CP);
279 void updatePrunedSubRanges(LiveInterval &LI);
288 void addUndefFlag(
const LiveInterval &
Int, SlotIndex UseIdx,
289 MachineOperand &MO,
unsigned SubRegIdx);
295 MachineInstr *eliminateUndefCopy(MachineInstr *CopyMI);
309 bool applyTerminalRule(
const MachineInstr &Copy)
const;
315 SmallVectorImpl<MachineInstr *> *
Dead =
nullptr,
318 if (LIS->shrinkToUses(LI,
Dead, SubRangeMask)) {
322 LIS->splitSeparateComponents(*LI, SplitLIs);
330 void deleteInstr(MachineInstr *
MI) {
331 ErasedInstrs.insert(
MI);
332 LIS->RemoveMachineInstrFromMaps(*
MI);
333 MI->eraseFromParent();
342 void checkMergingChangesDbgValues(CoalescerPair &CP,
LiveRange &
LHS,
350 RegisterCoalescer(
const CodeGenOptions &Opts, LiveIntervals *LIS,
351 SlotIndexes *SI,
const MachineLoopInfo *Loops,
352 const RegisterClassInfo *RegClassInfo)
353 : Opts(Opts), LIS(LIS), SI(SI), Loops(Loops), RegClassInfo(RegClassInfo) {
363 RegisterCoalescerLegacy() : MachineFunctionPass(ID) {}
365 void getAnalysisUsage(AnalysisUsage &AU)
const override;
367 MachineFunctionProperties getClearedProperties()
const override {
368 return MachineFunctionProperties().setIsSSA();
377char RegisterCoalescerLegacy::ID = 0;
382 "Register Coalescer",
false,
false)
395 Dst = MI->getOperand(0).getReg();
396 DstSub = MI->getOperand(0).getSubReg();
397 Src = MI->getOperand(1).getReg();
398 SrcSub = MI->getOperand(1).getSubReg();
399 }
else if (
MI->isSubregToReg()) {
400 Dst = MI->getOperand(0).getReg();
401 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),
402 MI->getOperand(2).getImm());
403 Src = MI->getOperand(1).getReg();
404 SrcSub = MI->getOperand(1).getSubReg();
416 if (
MBB->pred_size() != 1 ||
MBB->succ_size() != 1)
419 for (
const auto &
MI : *
MBB) {
420 if (!
MI.isCopyLike() && !
MI.isUnconditionalBranch())
430 Flipped = CrossClass =
false;
433 unsigned SrcSub = 0, DstSub = 0;
436 Partial = SrcSub || DstSub;
439 if (Src.isPhysical()) {
440 if (Dst.isPhysical())
450 if (Dst.isPhysical()) {
453 Dst = TRI.getSubReg(Dst, DstSub);
461 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, SrcRC);
472 if (SrcSub && DstSub) {
474 if (Src == Dst && SrcSub != DstSub)
477 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, SrcIdx,
484 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
488 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
491 NewRC = TRI.getCommonSubClass(DstRC, SrcRC);
500 if (DstIdx && !SrcIdx) {
506 CrossClass = NewRC != DstRC || NewRC != SrcRC;
509 assert(Src.isVirtual() &&
"Src must be virtual");
510 assert(!(Dst.isPhysical() && DstSub) &&
"Cannot have a physical SubIdx");
517 if (DstReg.isPhysical())
529 unsigned SrcSub = 0, DstSub = 0;
537 }
else if (Src != SrcReg) {
542 if (DstReg.isPhysical()) {
543 if (!Dst.isPhysical())
545 assert(!DstIdx && !SrcIdx &&
"Inconsistent CoalescerPair state.");
548 Dst = TRI.getSubReg(Dst, DstSub);
551 return DstReg == Dst;
553 return Register(TRI.getSubReg(DstReg, SrcSub)) == Dst;
560 return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
561 TRI.composeSubRegIndices(DstIdx, DstSub);
564void RegisterCoalescerLegacy::getAnalysisUsage(
AnalysisUsage &AU)
const {
575void RegisterCoalescer::eliminateDeadDefs(
LiveRangeEdit *Edit) {
585void RegisterCoalescer::LRE_WillEraseInstruction(
MachineInstr *
MI) {
590bool RegisterCoalescer::adjustCopiesBackFrom(
const CoalescerPair &CP,
593 assert(!CP.
isPhys() &&
"This doesn't work for physreg copies.");
618 if (BS == IntB.
end())
620 VNInfo *BValNo = BS->valno;
625 if (BValNo->
def != CopyIdx)
632 if (AS == IntA.
end())
634 VNInfo *AValNo = AS->valno;
646 if (ValS == IntB.
end())
664 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
668 BValNo->
def = FillerStart;
676 if (BValNo != ValS->valno)
685 S.removeSegment(*SS,
true);
689 if (!S.getVNInfoAt(FillerStart)) {
692 S.extendInBlock(BBStart, FillerStart);
694 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
697 if (SubBValNo != SubValSNo)
698 S.MergeValueNumberInto(SubBValNo, SubValSNo);
715 bool RecomputeLiveRange = AS->end == CopyIdx;
716 if (!RecomputeLiveRange) {
719 if (SS != S.end() &&
SS->end == CopyIdx) {
720 RecomputeLiveRange =
true;
725 if (RecomputeLiveRange)
732bool RegisterCoalescer::hasOtherReachingDefs(
LiveInterval &IntA,
741 if (ASeg.
valno != AValNo)
744 if (BI != IntB.
begin())
746 for (; BI != IntB.
end() && ASeg.
end >= BI->start; ++BI) {
747 if (BI->valno == BValNo)
749 if (BI->start <= ASeg.
start && BI->end > ASeg.
start)
751 if (BI->start > ASeg.
start && BI->start < ASeg.
end)
765 bool MergedWithDead =
false;
767 if (S.
valno != SrcValNo)
778 MergedWithDead =
true;
781 return std::make_pair(
Changed, MergedWithDead);
785RegisterCoalescer::removeCopyByCommutingDef(
const CoalescerPair &CP,
818 assert(BValNo !=
nullptr && BValNo->
def == CopyIdx);
824 return {
false,
false};
827 return {
false,
false};
829 return {
false,
false};
836 return {
false,
false};
842 return DefMO.getReg() == IntA.reg() && !DefMO.getSubReg();
844 return {
false,
false};
856 if (!
TII->findCommutedOpIndices(*
DefMI, UseOpIdx, NewDstIdx))
857 return {
false,
false};
862 return {
false,
false};
866 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
867 return {
false,
false};
877 if (US == IntA.
end() || US->valno != AValNo)
881 return {
false,
false};
891 TII->commuteInstruction(*
DefMI,
false, UseOpIdx, NewDstIdx);
893 return {
false,
false};
896 return {
false,
false};
897 if (NewMI !=
DefMI) {
922 UseMO.setReg(NewReg);
927 assert(US != IntA.
end() &&
"Use must be live");
928 if (US->valno != AValNo)
931 UseMO.setIsKill(
false);
933 UseMO.substPhysReg(NewReg, *
TRI);
935 UseMO.setReg(NewReg);
954 VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
957 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
959 S.MergeValueNumberInto(SubDVNI, SubBValNo);
967 bool ShrinkB =
false;
981 VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
990 MaskA |= SA.LaneMask;
996 VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)
997 : SR.getVNInfoAt(CopyIdx);
998 assert(BSubValNo != nullptr);
999 auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
1000 ShrinkB |= P.second;
1002 BSubValNo->def = ASubValNo->def;
1010 if ((SB.LaneMask & MaskA).any())
1014 SB.removeSegment(*S,
true);
1018 BValNo->
def = AValNo->
def;
1020 ShrinkB |=
P.second;
1027 return {
true, ShrinkB};
1077bool RegisterCoalescer::removePartialRedundancy(
const CoalescerPair &CP,
1110 bool FoundReverseCopy =
false;
1129 bool ValB_Changed =
false;
1130 for (
auto *VNI : IntB.
valnos) {
1131 if (VNI->isUnused())
1134 ValB_Changed =
true;
1142 FoundReverseCopy =
true;
1146 if (!FoundReverseCopy)
1156 if (CopyLeftBB && CopyLeftBB->
succ_size() > 1)
1167 if (InsPos != CopyLeftBB->
end()) {
1173 LLVM_DEBUG(
dbgs() <<
"\tremovePartialRedundancy: Move the copy to "
1178 TII->get(TargetOpcode::COPY), IntB.
reg())
1189 ErasedInstrs.
erase(NewCopyMI);
1191 LLVM_DEBUG(
dbgs() <<
"\tremovePartialRedundancy: Remove the copy from "
1202 deleteInstr(&CopyMI);
1218 if (!IntB.
liveAt(UseIdx))
1219 MO.setIsUndef(
true);
1229 VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1230 assert(BValNo &&
"All sublanes should be live");
1239 for (
unsigned I = 0;
I != EndPoints.
size();) {
1241 EndPoints[
I] = EndPoints.
back();
1260bool RegisterCoalescer::reMaterializeDef(
const CoalescerPair &CP,
1279 assert(
DefMI &&
"Defining instruction disappeared!");
1287 if (!
TII->isReMaterializable(*
DefMI))
1290 bool SawStore =
false;
1294 if (
MCID.getNumDefs() != 1)
1302 if (SrcIdx && DstIdx)
1318 for (MCRegUnit Unit :
TRI->regunits(DstReg)) {
1343 LiveRangeEdit Edit(&SrcInt, NewRegs, *MF, *LIS,
nullptr,
this);
1359 "Shouldn't have SrcIdx+DstIdx at this point");
1362 TRI->getCommonSubClass(DefRC, DstRC);
1363 if (CommonRC !=
nullptr) {
1371 if (MO.isReg() && MO.getReg() == DstReg && MO.getSubReg() == DstIdx) {
1392 "No explicit operands after implicit operands.");
1395 "unexpected implicit virtual register def");
1401 ErasedInstrs.
insert(CopyMI);
1439 "subrange update for implicit-def of super register may not be "
1440 "properly handled");
1450 NewRC == (NewIdx ?
TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx)
1451 :
TRI->getCommonSubClass(NewRC, DefRC))) &&
1452 "Subreg chosen for remat incompatible with instruction!");
1459 SR.LaneMask =
TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1462 updateRegDefsUses(DstReg, DstReg, DstIdx);
1511 LaneBitmask DstMask = NewIdx ?
TRI->getSubRegIndexLaneMask(NewIdx)
1527 if (!SR.
liveAt(DefIndex))
1534 bool UpdatedSubRanges =
false;
1536 if ((SR.
LaneMask & DstMask).none()) {
1538 <<
"Removing undefined SubRange "
1551 UpdatedSubRanges =
true;
1554 if (UpdatedSubRanges)
1568 bool HasDefMatchingCopy =
false;
1569 for (
auto [OpIndex,
Reg] : NewMIImplDefs) {
1575 if (DstReg != CopyDstReg)
1578 HasDefMatchingCopy =
true;
1582 if (!HasDefMatchingCopy)
1584 CopyDstReg,
true ,
true ,
false ));
1628 UseMO.substPhysReg(DstReg, *
TRI);
1630 UseMO.setReg(DstReg);
1638 if (ToBeUpdated.
count(SrcReg))
1641 unsigned NumCopyUses = 0;
1643 if (UseMO.getParent()->isCopyLike())
1646 if (NumCopyUses < Opts.late_remat_update_threshold) {
1649 if (!DeadDefs.
empty())
1650 eliminateDeadDefs(&Edit);
1652 ToBeUpdated.
insert(SrcReg);
1670 unsigned SrcSubIdx = 0, DstSubIdx = 0;
1671 if (!
isMoveInstr(*
TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
1680 if ((SR.
LaneMask & SrcMask).none())
1685 }
else if (SrcLI.
liveAt(Idx))
1693 assert(Seg !=
nullptr &&
"No segment for defining instruction");
1698 if (((
V &&
V->isPHIDef()) || (!
V && !DstLI.
liveAt(Idx)))) {
1706 CopyMI->
getOpcode() == TargetOpcode::SUBREG_TO_REG);
1711 CopyMI->
setDesc(
TII->get(TargetOpcode::IMPLICIT_DEF));
1728 if ((SR.
LaneMask & DstMask).none())
1752 if ((SR.
LaneMask & UseMask).none())
1760 isLive = DstLI.
liveAt(UseIdx);
1773 if (MO.
getReg() == DstReg)
1785 bool IsUndef =
true;
1787 if ((S.LaneMask & Mask).none())
1789 if (S.liveAt(UseIdx)) {
1802 ShrinkMainRange =
true;
1811 if (DstInt && DstReg != SrcReg) {
1817 if (SubReg == 0 && MO.
isDef())
1823 addUndefFlag(*DstInt, UseIdx, MO, SubReg);
1824 }
else if (MO.
isUse() && SubReg == 0 && !DstInt->
liveAt(UseIdx)) {
1846 if (SrcReg == DstReg && !Visited.
insert(
UseMI).second)
1859 for (
unsigned Op :
Ops) {
1865 if (SubIdx && MO.
isDef())
1871 unsigned SubUseIdx =
TRI->composeSubRegIndices(SubIdx, MO.
getSubReg());
1889 addUndefFlag(*DstInt, UseIdx, MO, SubUseIdx);
1900 dbgs() <<
"\t\tupdated: ";
1908bool RegisterCoalescer::canJoinPhys(
const CoalescerPair &CP) {
1913 LLVM_DEBUG(
dbgs() <<
"\tCan only merge into reserved registers.\n");
1922 dbgs() <<
"\tCannot join complex intervals into reserved register.\n");
1926bool RegisterCoalescer::copyValueUndefInPredecessors(
1940void RegisterCoalescer::setUndefOnPrunedSubRegUses(
LiveInterval &LI,
1947 if (SubRegIdx == 0 || MO.
isUndef())
1953 if (!S.
liveAt(Pos) && (PrunedLanes & SubRegMask).any()) {
1969void RegisterCoalescer::updatePrunedSubRanges(
LiveInterval &LI) {
1972 for (
auto [Mask, Idx] : PHIKills) {
1973 if ((Mask & S.LaneMask).any() && LI.
liveAt(
Idx.getPrevSlot()))
1977 if (!EndPoints.
empty()) {
1984 if ((S.LaneMask & ShrinkMask).any())
1985 ShrinkMainRange =
true;
1991RegisterCoalescer::JoinResult RegisterCoalescer::joinCopy(
1999 return JoinResult::Rejected;
2005 <<
"are available for allocation\n");
2006 return JoinResult::Rejected;
2017 if (!
TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
2020 return JoinResult::Rejected;
2030 eliminateDeadDefs();
2031 return JoinResult::Joined;
2037 if (
MachineInstr *UndefMI = eliminateUndefCopy(CopyMI)) {
2038 if (UndefMI->isImplicitDef())
2039 return JoinResult::Rejected;
2040 deleteInstr(CopyMI);
2041 return JoinResult::Rejected;
2050 LLVM_DEBUG(
dbgs() <<
"\tCopy already coalesced: " << LI <<
'\n');
2055 assert(ReadVNI &&
"No value before copy and no <undef> flag.");
2056 assert(ReadVNI != DefVNI &&
"Cannot read and define the same value.");
2071 if (copyValueUndefInPredecessors(S,
MBB, SLRQ)) {
2072 LLVM_DEBUG(
dbgs() <<
"Incoming sublane value is undef at copy\n");
2073 PrunedLanes |= S.LaneMask;
2080 if (PrunedLanes.
any()) {
2081 LLVM_DEBUG(
dbgs() <<
"Pruning undef incoming lanes: " << PrunedLanes
2083 setUndefOnPrunedSubRegUses(LI, CP.
getSrcReg(), PrunedLanes);
2088 deleteInstr(CopyMI);
2089 return JoinResult::Joined;
2097 if (!canJoinPhys(CP)) {
2100 bool IsDefCopy =
false;
2101 if (reMaterializeDef(CP, CopyMI, IsDefCopy))
2102 return JoinResult::Joined;
2104 return JoinResult::Deferred;
2105 return JoinResult::Rejected;
2114 dbgs() <<
"\tConsidering merging to "
2115 <<
TRI->getRegClassName(CP.
getNewRC()) <<
" with ";
2128 ShrinkMainRange =
false;
2135 JoinResult
Result = joinIntervals(CP);
2136 if (Result != JoinResult::Joined) {
2140 bool IsDefCopy =
false;
2141 if (reMaterializeDef(CP, CopyMI, IsDefCopy))
2142 return JoinResult::Joined;
2147 bool Changed = adjustCopiesBackFrom(CP, CopyMI);
2148 bool Shrink =
false;
2150 std::tie(
Changed, Shrink) = removeCopyByCommutingDef(CP, CopyMI);
2152 deleteInstr(CopyMI);
2160 return JoinResult::Joined;
2167 if (removePartialRedundancy(CP, *CopyMI))
2168 return JoinResult::Joined;
2175 if (Result == JoinResult::Deferred)
2195 if (ErasedInstrs.
erase(CopyMI))
2197 CurrentErasedInstrs.
insert(CopyMI);
2205 if (ShrinkMask.
any() || !PHIKills.empty())
2213 else if (ShrinkMainRange)
2226 dbgs() <<
"\tResult = ";
2235 return JoinResult::Joined;
2238bool RegisterCoalescer::joinReservedPhysReg(
CoalescerPair &CP) {
2246 assert(
RHS.containsOneValue() &&
"Invalid join with reserved register");
2256 for (MCRegUnit Unit :
TRI->regunits(DstReg)) {
2272 !RegMaskUsable.
test(DstReg.
id())) {
2294 deleteInstr(CopyMI);
2316 bool IsEarlyClobber =
2327 if (
MI.isDebugInstr())
2329 if (
MI.readsRegister(DstReg,
TRI)) {
2339 <<
printReg(DstReg,
TRI) <<
" at " << CopyRegIdx <<
"\n");
2342 deleteInstr(CopyMI);
2345 for (MCRegUnit Unit :
TRI->regunits(DstReg)) {
2434 const unsigned SubIdx;
2438 const LaneBitmask LaneMask;
2442 const bool SubRangeJoin;
2445 const bool TrackSubRegLiveness;
2448 SmallVectorImpl<VNInfo *> &NewVNInfo;
2450 const CoalescerPair &CP;
2452 SlotIndexes *Indexes;
2453 const TargetRegisterInfo *
TRI;
2457 SmallVector<int, 8> Assignments;
2461 enum ConflictResolution {
2493 ConflictResolution Resolution = CR_Keep;
2496 LaneBitmask WriteLanes;
2500 LaneBitmask ValidLanes;
2503 VNInfo *RedefVNI =
nullptr;
2506 VNInfo *OtherVNI =
nullptr;
2519 bool ErasableImplicitDef =
false;
2523 bool Pruned =
false;
2526 bool PrunedComputed =
false;
2533 bool Identical =
false;
2537 bool isAnalyzed()
const {
return WriteLanes.
any(); }
2541 void mustKeepImplicitDef(
const TargetRegisterInfo &
TRI,
2542 const MachineInstr &ImpDef) {
2544 ErasableImplicitDef =
false;
2556 LaneBitmask computeWriteLanes(
const MachineInstr *
DefMI,
bool &Redef)
const;
2559 std::pair<const VNInfo *, Register> followCopyChain(
const VNInfo *VNI)
const;
2561 bool valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2562 const JoinVals &
Other)
const;
2571 ConflictResolution analyzeValue(
unsigned ValNo, JoinVals &
Other);
2576 void computeAssignment(
unsigned ValNo, JoinVals &
Other);
2594 taintExtent(
unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &
Other,
2595 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2599 bool usesLanes(
const MachineInstr &
MI,
Register,
unsigned, LaneBitmask)
const;
2607 bool isPrunedValue(
unsigned ValNo, JoinVals &
Other);
2611 SmallVectorImpl<VNInfo *> &newVNInfo,
const CoalescerPair &cp,
2612 LiveIntervals *lis,
const TargetRegisterInfo *
TRI,
bool SubRangeJoin,
2613 bool TrackSubRegLiveness)
2614 : LR(LR),
Reg(
Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2615 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2616 NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2617 TRI(
TRI), Assignments(LR.getNumValNums(), -1),
2618 Vals(LR.getNumValNums()) {}
2622 bool mapValues(JoinVals &
Other);
2626 bool resolveConflicts(JoinVals &
Other);
2631 void pruneValues(JoinVals &
Other, SmallVectorImpl<SlotIndex> &EndPoints,
2637 void pruneSubRegValues(
2638 LiveInterval &LI, LaneBitmask &ShrinkMask,
2639 SmallVectorImpl<std::pair<LaneBitmask, SlotIndex>> &PHIKills);
2648 void pruneMainSegments(LiveInterval &LI,
bool &ShrinkMainRange);
2654 void eraseInstrs(SmallPtrSetImpl<MachineInstr *> &ErasedInstrs,
2655 SmallVectorImpl<Register> &ShrinkRegs,
2656 LiveInterval *LI =
nullptr);
2659 void removeImplicitDefs();
2662 const int *getAssignments()
const {
return Assignments.
data(); }
2665 ConflictResolution getResolution(
unsigned Num)
const {
2666 return Vals[Num].Resolution;
2673 bool &Redef)
const {
2678 L |=
TRI->getSubRegIndexLaneMask(
2686std::pair<const VNInfo *, Register>
2687JoinVals::followCopyChain(
const VNInfo *VNI)
const {
2693 assert(
MI &&
"No defining instruction");
2694 if (!
MI->isFullCopy())
2695 return std::make_pair(VNI, TrackReg);
2696 Register SrcReg =
MI->getOperand(1).getReg();
2698 return std::make_pair(VNI, TrackReg);
2712 LaneBitmask SMask =
TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2713 if ((SMask & LaneMask).
none())
2721 return std::make_pair(VNI, TrackReg);
2724 if (ValueIn ==
nullptr) {
2731 return std::make_pair(
nullptr, SrcReg);
2736 return std::make_pair(VNI, TrackReg);
2739bool JoinVals::valuesIdentical(
VNInfo *Value0,
VNInfo *Value1,
2740 const JoinVals &
Other)
const {
2743 std::tie(Orig0, Reg0) = followCopyChain(Value0);
2744 if (Orig0 == Value1 && Reg0 ==
Other.Reg)
2749 std::tie(Orig1, Reg1) =
Other.followCopyChain(Value1);
2753 if (Orig0 ==
nullptr || Orig1 ==
nullptr)
2754 return Orig0 == Orig1 && Reg0 == Reg1;
2760 return Orig0->
def == Orig1->
def && Reg0 == Reg1;
2763JoinVals::ConflictResolution JoinVals::analyzeValue(
unsigned ValNo,
2765 Val &
V = Vals[ValNo];
2766 assert(!
V.isAnalyzed() &&
"Value has already been analyzed!");
2778 :
TRI->getSubRegIndexLaneMask(SubIdx);
2779 V.ValidLanes =
V.WriteLanes = Lanes;
2788 V.ErasableImplicitDef =
true;
2792 V.ValidLanes =
V.WriteLanes = computeWriteLanes(
DefMI, Redef);
2811 assert((TrackSubRegLiveness ||
V.RedefVNI) &&
2812 "Instruction is reading nonexistent value");
2813 if (
V.RedefVNI !=
nullptr) {
2814 computeAssignment(
V.RedefVNI->id,
Other);
2815 V.ValidLanes |= Vals[
V.RedefVNI->id].ValidLanes;
2827 V.ErasableImplicitDef =
true;
2844 if (OtherVNI->
def < VNI->
def)
2845 Other.computeAssignment(OtherVNI->
id, *
this);
2850 return CR_Impossible;
2852 V.OtherVNI = OtherVNI;
2853 Val &OtherV =
Other.Vals[OtherVNI->
id];
2857 if (!OtherV.isAnalyzed() ||
Other.Assignments[OtherVNI->
id] == -1)
2864 if ((
V.ValidLanes & OtherV.ValidLanes).any())
2866 return CR_Impossible;
2880 Other.computeAssignment(
V.OtherVNI->id, *
this);
2881 Val &OtherV =
Other.Vals[
V.OtherVNI->id];
2883 if (OtherV.ErasableImplicitDef) {
2903 <<
", keeping it.\n");
2904 OtherV.mustKeepImplicitDef(*
TRI, *OtherImpDef);
2911 dbgs() <<
"IMPLICIT_DEF defined at " <<
V.OtherVNI->def
2912 <<
" may be live into EH pad successors, keeping it.\n");
2913 OtherV.mustKeepImplicitDef(*
TRI, *OtherImpDef);
2916 OtherV.ValidLanes &= ~OtherV.WriteLanes;
2934 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2949 valuesIdentical(VNI,
V.OtherVNI,
Other)) {
2972 if ((
V.WriteLanes & OtherV.ValidLanes).none())
2985 "Only early clobber defs can overlap a kill");
2986 return CR_Impossible;
2993 if ((
TRI->getSubRegIndexLaneMask(
Other.SubIdx) & ~
V.WriteLanes).none())
2994 return CR_Impossible;
2996 if (TrackSubRegLiveness) {
3001 if (!OtherLI.hasSubRanges()) {
3003 return (OtherMask &
V.WriteLanes).none() ? CR_Replace : CR_Impossible;
3011 TRI->composeSubRegIndexLaneMask(
Other.SubIdx, OtherSR.LaneMask);
3012 if ((OtherMask &
V.WriteLanes).none())
3015 auto OtherSRQ = OtherSR.Query(VNI->
def);
3016 if (OtherSRQ.valueIn() && OtherSRQ.endPoint() > VNI->
def) {
3018 return CR_Impossible;
3031 return CR_Impossible;
3040 return CR_Unresolved;
3043void JoinVals::computeAssignment(
unsigned ValNo, JoinVals &
Other) {
3044 Val &
V = Vals[ValNo];
3045 if (
V.isAnalyzed()) {
3048 assert(Assignments[ValNo] != -1 &&
"Bad recursion?");
3051 switch ((
V.Resolution = analyzeValue(ValNo,
Other))) {
3055 assert(
V.OtherVNI &&
"OtherVNI not assigned, can't merge.");
3056 assert(
Other.Vals[
V.OtherVNI->id].isAnalyzed() &&
"Missing recursion");
3057 Assignments[ValNo] =
Other.Assignments[
V.OtherVNI->id];
3061 <<
V.OtherVNI->def <<
" --> @"
3062 << NewVNInfo[Assignments[ValNo]]->def <<
'\n');
3065 case CR_Unresolved: {
3067 assert(
V.OtherVNI &&
"OtherVNI not assigned, can't prune");
3068 Val &OtherV =
Other.Vals[
V.OtherVNI->id];
3069 OtherV.Pruned =
true;
3074 Assignments[ValNo] = NewVNInfo.
size();
3080bool JoinVals::mapValues(JoinVals &
Other) {
3082 computeAssignment(i,
Other);
3083 if (Vals[i].Resolution == CR_Impossible) {
3092bool JoinVals::taintExtent(
3101 assert(OtherI !=
Other.LR.end() &&
"No conflict?");
3106 if (
End >= MBBEnd) {
3108 << OtherI->valno->id <<
'@' << OtherI->start <<
'\n');
3112 << OtherI->valno->id <<
'@' << OtherI->start <<
" to "
3117 TaintExtent.push_back(std::make_pair(
End, TaintedLanes));
3120 if (++OtherI ==
Other.LR.end() || OtherI->start >= MBBEnd)
3124 const Val &OV =
Other.Vals[OtherI->valno->id];
3125 TaintedLanes &= ~OV.WriteLanes;
3128 }
while (TaintedLanes.
any());
3134 if (
MI.isDebugOrPseudoInstr())
3141 unsigned S =
TRI->composeSubRegIndices(SubIdx, MO.
getSubReg());
3142 if ((Lanes &
TRI->getSubRegIndexLaneMask(S)).any())
3148bool JoinVals::resolveConflicts(JoinVals &
Other) {
3151 assert(
V.Resolution != CR_Impossible &&
"Unresolvable conflict");
3152 if (
V.Resolution != CR_Unresolved)
3161 assert(
V.OtherVNI &&
"Inconsistent conflict resolution.");
3163 const Val &OtherV =
Other.Vals[
V.OtherVNI->id];
3168 LaneBitmask TaintedLanes =
V.WriteLanes & OtherV.ValidLanes;
3170 if (!taintExtent(i, TaintedLanes,
Other, TaintExtent))
3174 assert(!TaintExtent.
empty() &&
"There should be at least one conflict.");
3187 "Interference ends on VNI->def. Should have been handled earlier");
3190 assert(LastMI &&
"Range must end at a proper instruction");
3191 unsigned TaintNum = 0;
3194 if (usesLanes(*
MI,
Other.Reg,
Other.SubIdx, TaintedLanes)) {
3199 if (&*
MI == LastMI) {
3200 if (++TaintNum == TaintExtent.
size())
3203 assert(LastMI &&
"Range must end at a proper instruction");
3204 TaintedLanes = TaintExtent[TaintNum].second;
3210 V.Resolution = CR_Replace;
3216bool JoinVals::isPrunedValue(
unsigned ValNo, JoinVals &
Other) {
3217 Val &
V = Vals[ValNo];
3218 if (
V.Pruned ||
V.PrunedComputed)
3221 if (
V.Resolution != CR_Erase &&
V.Resolution != CR_Merge)
3226 V.PrunedComputed =
true;
3227 V.Pruned =
Other.isPrunedValue(
V.OtherVNI->id, *
this);
3231void JoinVals::pruneValues(JoinVals &
Other,
3233 bool changeInstrs) {
3236 switch (Vals[i].Resolution) {
3247 Val &OtherV =
Other.Vals[Vals[i].OtherVNI->id];
3248 bool EraseImpDef = OtherV.ErasableImplicitDef &&
3249 OtherV.Resolution == CR_Keep &&
3250 OtherV.ValidLanes.none();
3251 if (!
Def.isBlock()) {
3271 <<
": " <<
Other.LR <<
'\n');
3276 if (isPrunedValue(i,
Other)) {
3281 Val &OtherV =
Other.Vals[Vals[i].OtherVNI->id];
3288 bool EraseImpDef = OtherV.ErasableImplicitDef &&
3289 OtherV.Resolution == CR_Keep &&
3290 OtherV.ValidLanes.none();
3291 LIS->
pruneValue(LR, Def, EraseImpDef ?
nullptr : &EndPoints);
3293 << Def <<
": " << LR <<
'\n');
3309 if (
PHI->isUnused() || !
PHI->isPHIDef())
3366void JoinVals::pruneSubRegValues(
3370 bool DidPrune =
false;
3375 if (
V.Resolution != CR_Erase &&
3376 (
V.Resolution != CR_Keep || !
V.ErasableImplicitDef || !
V.Pruned))
3383 OtherDef =
V.OtherVNI->def;
3386 LLVM_DEBUG(
dbgs() <<
"\t\tExpecting instruction removal at " << Def
3394 if (ValueOut !=
nullptr &&
3396 (
V.Identical &&
V.Resolution == CR_Erase && ValueOut->
def == Def))) {
3398 <<
" at " << Def <<
"\n");
3405 if (ValueOut->
def == Def)
3408 if (
V.Identical && S.Query(OtherDef).valueOutOrDead()) {
3415 PHIKills.emplace_back(S.LaneMask,
Kill);
3421 ShrinkMask |= S.LaneMask;
3435 ShrinkMask |= S.LaneMask;
3447 if (VNI->
def == Def)
3453void JoinVals::pruneMainSegments(
LiveInterval &LI,
bool &ShrinkMainRange) {
3457 if (Vals[i].Resolution != CR_Keep)
3462 Vals[i].Pruned =
true;
3463 ShrinkMainRange =
true;
3467void JoinVals::removeImplicitDefs() {
3470 if (
V.Resolution != CR_Keep || !
V.ErasableImplicitDef || !
V.Pruned)
3486 switch (Vals[i].Resolution) {
3491 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
3503 if (LI !=
nullptr) {
3528 ED = ED.
isValid() ? std::min(ED,
I->start) :
I->start;
3530 LE =
LE.isValid() ? std::max(LE,
I->end) :
I->
end;
3533 NewEnd = std::min(NewEnd, LE);
3535 NewEnd = std::min(NewEnd, ED);
3541 if (S != LR.
begin())
3542 std::prev(S)->end = NewEnd;
3546 dbgs() <<
"\t\tremoved " << i <<
'@' <<
Def <<
": " << LR <<
'\n';
3548 dbgs() <<
"\t\t LHS = " << *LI <<
'\n';
3555 assert(
MI &&
"No instruction to erase");
3564 MI->eraseFromParent();
3578 CP, LIS,
TRI,
true,
true);
3580 CP, LIS,
TRI,
true,
true);
3587 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
3592 if (!LHSVals.resolveConflicts(RHSVals) ||
3593 !RHSVals.resolveConflicts(LHSVals)) {
3604 LHSVals.pruneValues(RHSVals, EndPoints,
false);
3605 RHSVals.pruneValues(LHSVals, EndPoints,
false);
3607 LHSVals.removeImplicitDefs();
3608 RHSVals.removeImplicitDefs();
3613 LRange.
join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
3618 if (EndPoints.
empty())
3624 dbgs() <<
"\t\trestoring liveness to " << EndPoints.
size() <<
" points: ";
3625 for (
unsigned i = 0, n = EndPoints.
size(); i != n; ++i) {
3626 dbgs() << EndPoints[i];
3630 dbgs() <<
": " << LRange <<
'\n';
3635void RegisterCoalescer::mergeSubRangeInto(
LiveInterval &LI,
3639 unsigned ComposeSubRegIdx) {
3649 joinSubRegRanges(SR, RangeCopy, SR.
LaneMask, CP);
3659bool RegisterCoalescer::isHighCostLiveInterval(
LiveInterval &LI) {
3660 if (LI.
valnos.
size() < Opts.large_interval_size_threshold)
3662 auto &Counter = LargeLIVisitCounter[LI.
reg()];
3663 if (Counter < Opts.large_interval_freq_threshold) {
3670RegisterCoalescer::JoinResult
3677 NewVNInfo, CP, LIS,
TRI,
false, TrackSubRegLiveness);
3679 NewVNInfo, CP, LIS,
TRI,
false, TrackSubRegLiveness);
3683 if (isHighCostLiveInterval(
LHS) || isHighCostLiveInterval(
RHS)) {
3685 <<
RHS.valnos.size() <<
", segments=" <<
RHS.size()
3686 <<
"; LHS valnos=" <<
LHS.valnos.size()
3687 <<
", segments=" <<
LHS.size() <<
'\n');
3688 return JoinResult::Rejected;
3694 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
3695 return JoinResult::Deferred;
3699 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
3700 return JoinResult::Deferred;
3703 if (
RHS.hasSubRanges() ||
LHS.hasSubRanges()) {
3709 if (!
LHS.hasSubRanges()) {
3711 :
TRI->getSubRegIndexLaneMask(DstIdx);
3715 }
else if (DstIdx != 0) {
3727 if (!
RHS.hasSubRanges()) {
3729 :
TRI->getSubRegIndexLaneMask(SrcIdx);
3730 mergeSubRangeInto(
LHS,
RHS, Mask, CP, DstIdx);
3735 mergeSubRangeInto(
LHS, R, Mask, CP, DstIdx);
3742 LHSVals.pruneMainSegments(
LHS, ShrinkMainRange);
3744 LHSVals.pruneSubRegValues(
LHS, ShrinkMask, PHIKills);
3745 RHSVals.pruneSubRegValues(
LHS, ShrinkMask, PHIKills);
3751 LHSVals.pruneMainSegments(
LHS, ShrinkMainRange);
3752 LHSVals.pruneSubRegValues(
LHS, ShrinkMask, PHIKills);
3760 LHSVals.pruneValues(RHSVals, EndPoints,
true);
3761 RHSVals.pruneValues(LHSVals, EndPoints,
true);
3766 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &
LHS);
3767 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3768 while (!ShrinkRegs.
empty())
3772 checkMergingChangesDbgValues(CP,
LHS, LHSVals,
RHS, RHSVals);
3777 if (RegIt != RegToPHIIdx.
end()) {
3779 for (
unsigned InstID : RegIt->second) {
3780 auto PHIIt = PHIValToPos.
find(InstID);
3785 auto LII =
RHS.find(
SI);
3786 if (LII ==
RHS.end() || LII->start >
SI)
3804 if (PHIIt->second.SubReg && PHIIt->second.SubReg != CP.
getSrcIdx())
3819 auto InstrNums = RegIt->second;
3820 RegToPHIIdx.
erase(RegIt);
3825 if (RegIt != RegToPHIIdx.
end())
3832 LHS.join(
RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3834 if (!EndPoints.
empty()) {
3838 dbgs() <<
"\t\trestoring liveness to " << EndPoints.
size() <<
" points: ";
3839 for (
unsigned i = 0, n = EndPoints.
size(); i != n; ++i) {
3840 dbgs() << EndPoints[i];
3844 dbgs() <<
": " <<
LHS <<
'\n';
3849 return JoinResult::Joined;
3852RegisterCoalescer::JoinResult
3855 return joinReservedPhysReg(CP) ? JoinResult::Joined : JoinResult::Deferred;
3856 return joinVirtRegs(CP);
3866 for (
auto *
X : ToInsert) {
3867 for (
const auto &
Op :
X->debug_operands()) {
3868 if (
Op.isReg() &&
Op.getReg().isVirtual())
3869 DbgVRegToValues[
Op.getReg()].push_back({
Slot,
X});
3879 for (
auto &
MBB : MF) {
3882 for (
auto &
MI :
MBB) {
3883 if (
MI.isDebugValue()) {
3885 return MO.isReg() && MO.getReg().isVirtual();
3887 ToInsert.push_back(&
MI);
3888 }
else if (!
MI.isDebugOrPseudoInstr()) {
3890 CloseNewDVRange(CurrentSlot);
3899 for (
auto &Pair : DbgVRegToValues)
3903void RegisterCoalescer::checkMergingChangesDbgValues(
CoalescerPair &CP,
3907 JoinVals &RHSVals) {
3909 checkMergingChangesDbgValuesImpl(
Reg,
RHS,
LHS, LHSVals);
3913 checkMergingChangesDbgValuesImpl(
Reg,
LHS,
RHS, RHSVals);
3921void RegisterCoalescer::checkMergingChangesDbgValuesImpl(
Register Reg,
3924 JoinVals &RegVals) {
3926 auto VRegMapIt = DbgVRegToValues.
find(
Reg);
3927 if (VRegMapIt == DbgVRegToValues.
end())
3930 auto &DbgValueSet = VRegMapIt->second;
3931 auto DbgValueSetIt = DbgValueSet.begin();
3932 auto SegmentIt = OtherLR.
begin();
3934 bool LastUndefResult =
false;
3939 auto ShouldUndef = [&RegVals, &
RegLR, &LastUndefResult,
3944 if (LastUndefIdx == Idx)
3945 return LastUndefResult;
3951 auto OtherIt =
RegLR.find(Idx);
3952 if (OtherIt ==
RegLR.end())
3961 auto Resolution = RegVals.getResolution(OtherIt->valno->id);
3963 Resolution != JoinVals::CR_Keep && Resolution != JoinVals::CR_Erase;
3965 return LastUndefResult;
3971 while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.
end()) {
3972 if (DbgValueSetIt->first < SegmentIt->end) {
3975 if (DbgValueSetIt->first >= SegmentIt->start) {
3976 bool HasReg = DbgValueSetIt->second->hasDebugOperandForReg(
Reg);
3977 bool ShouldUndefReg = ShouldUndef(DbgValueSetIt->first);
3978 if (HasReg && ShouldUndefReg) {
3980 DbgValueSetIt->second->setDebugValueUndef();
3994struct MBBPriorityInfo {
3995 MachineBasicBlock *
MBB;
3999 MBBPriorityInfo(MachineBasicBlock *mbb,
unsigned depth,
bool issplit)
4000 :
MBB(mbb),
Depth(depth), IsSplit(issplit) {}
4010 const MBBPriorityInfo *
RHS) {
4012 if (
LHS->Depth !=
RHS->Depth)
4013 return LHS->Depth >
RHS->Depth ? -1 : 1;
4016 if (
LHS->IsSplit !=
RHS->IsSplit)
4017 return LHS->IsSplit ? -1 : 1;
4021 unsigned cl =
LHS->MBB->pred_size() +
LHS->MBB->succ_size();
4022 unsigned cr =
RHS->MBB->pred_size() +
RHS->MBB->succ_size();
4024 return cl > cr ? -1 : 1;
4027 return LHS->MBB->getNumber() <
RHS->MBB->getNumber() ? -1 : 1;
4032 if (!Copy->isCopy())
4035 if (Copy->getOperand(1).isUndef())
4038 Register SrcReg = Copy->getOperand(1).getReg();
4039 Register DstReg = Copy->getOperand(0).getReg();
4047void RegisterCoalescer::lateLiveIntervalUpdate() {
4053 if (!DeadDefs.
empty())
4054 eliminateDeadDefs();
4056 ToBeUpdated.
clear();
4059bool RegisterCoalescer::copyCoalesceWorkList(
4061 bool Progress =
false;
4072 JoinResult
Result = joinCopy(
MI, CurrentErasedInstrs);
4073 Progress |=
Result == JoinResult::Joined;
4074 if (Result != JoinResult::Deferred)
4078 if (!CurrentErasedInstrs.
empty()) {
4080 if (
MI && CurrentErasedInstrs.
count(
MI))
4084 if (
MI && CurrentErasedInstrs.
count(
MI))
4095 assert(Copy.isCopyLike());
4098 if (&
MI != &Copy &&
MI.isCopyLike())
4103bool RegisterCoalescer::applyTerminalRule(
const MachineInstr &Copy)
const {
4105 if (!Opts.terminal_rule)
4108 unsigned SrcSubReg = 0, DstSubReg = 0;
4109 if (!
isMoveInstr(*
TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg))
4130 if (&
MI == &Copy || !
MI.isCopyLike() ||
MI.getParent() != OrigBB)
4133 unsigned OtherSrcSubReg = 0, OtherSubReg = 0;
4137 if (OtherReg == SrcReg)
4138 OtherReg = OtherSrcReg;
4157 const unsigned PrevSize = WorkList.
size();
4158 if (JoinGlobalCopies) {
4164 if (!
MI.isCopyLike())
4166 bool ApplyTerminalRule = applyTerminalRule(
MI);
4168 if (ApplyTerminalRule)
4173 if (ApplyTerminalRule)
4180 LocalWorkList.
append(LocalTerminals.
begin(), LocalTerminals.
end());
4187 if (MII.isCopyLike()) {
4188 if (applyTerminalRule(MII))
4201 if (copyCoalesceWorkList(CurrList))
4203 std::remove(WorkList.
begin() + PrevSize, WorkList.
end(),
nullptr),
4207void RegisterCoalescer::coalesceLocals() {
4208 copyCoalesceWorkList(LocalWorkList);
4213 LocalWorkList.clear();
4216void RegisterCoalescer::joinAllIntervals() {
4217 LLVM_DEBUG(
dbgs() <<
"********** JOINING INTERVALS ***********\n");
4218 assert(WorkList.
empty() && LocalWorkList.empty() &&
"Old data still around.");
4220 std::vector<MBBPriorityInfo> MBBs;
4221 MBBs.reserve(MF->size());
4223 MBBs.push_back(MBBPriorityInfo(&
MBB,
Loops->getLoopDepth(&
MBB),
4226 llvm::sort(MBBs, [](
const MBBPriorityInfo &
LHS,
const MBBPriorityInfo &
RHS) {
4231 unsigned CurrDepth = std::numeric_limits<unsigned>::max();
4232 for (MBBPriorityInfo &
MBB : MBBs) {
4234 if (JoinGlobalCopies &&
MBB.Depth < CurrDepth) {
4236 CurrDepth =
MBB.Depth;
4238 copyCoalesceInMBB(
MBB.MBB);
4240 lateLiveIntervalUpdate();
4245 while (copyCoalesceWorkList(WorkList))
4247 lateLiveIntervalUpdate();
4268bool RegisterCoalescerLegacy::runOnMachineFunction(
MachineFunction &MF) {
4269 auto *LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
4270 auto *
Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
4271 auto *SIWrapper = getAnalysisIfAvailable<SlotIndexesWrapperPass>();
4272 auto *RegClassInfo =
4273 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
4274 SlotIndexes *
SI = SIWrapper ? &SIWrapper->getSI() :
nullptr;
4276 return Impl.run(MF);
4280 LLVM_DEBUG(
dbgs() <<
"********** REGISTER COALESCER **********\n"
4281 <<
"********** Function: " << fn.
getName() <<
'\n');
4293 dbgs() <<
"* Skipped as it exposes functions that returns twice.\n");
4311 unsigned SubReg = DebugPHI.second.SubReg;
4313 PHIValPos
P = {
SI,
Reg, SubReg};
4314 PHIValToPos.
insert(std::make_pair(DebugPHI.first,
P));
4315 RegToPHIIdx[
Reg].push_back(DebugPHI.first);
4321 JoinSplitEdges = Opts.join_splitedges;
4323 if (Opts.verify_coalescing)
4324 MF->
verify(LIS,
SI,
"Before register coalescing", &
errs());
4326 DbgVRegToValues.
clear();
4330 if (Opts.join_liveintervals)
4360 assert((S.LaneMask & ~MaxMask).none());
4371 auto it = PHIValToPos.
find(
p.first);
4373 p.second.Reg = it->second.Reg;
4374 p.second.SubReg = it->second.SubReg;
4377 PHIValToPos.
clear();
4378 RegToPHIIdx.
clear();
4382 if (Opts.verify_coalescing)
4383 MF->
verify(LIS,
SI,
"After register coalescing", &
errs());
MachineInstrBuilder & UseMI
MachineInstrBuilder MachineInstrBuilder & DefMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseSet and SmallDenseSet classes.
const HexagonInstrInfo * TII
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
A common definition of LaneBitmask for use in TableGen and CodeGen.
Register const TargetRegisterInfo * TRI
Promote Memory to Register
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
MachineRegisterInfo & MRI
static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS)
static bool isSplitEdge(const MachineBasicBlock *MBB)
Return true if this block should be vacated by the coalescer to eliminate branches.
static int compareMBBPriority(const MBBPriorityInfo *LHS, const MBBPriorityInfo *RHS)
C-style comparator that sorts first based on the loop depth of the basic block (the unsigned),...
static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def)
Check if any of the subranges of LI contain a definition at Def.
static std::pair< bool, bool > addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo, const LiveRange &Src, const VNInfo *SrcValNo)
Copy segments with value number SrcValNo from liverange Src to live range @Dst and use value number D...
static bool isLiveThrough(const LiveQueryResult Q)
static bool isTerminalReg(Register DstReg, const MachineInstr &Copy, const MachineRegisterInfo *MRI)
Check if DstReg is a terminal node.
static void collectPHIKills(const LiveRange &LR, const VNInfo *VNI, const SlotIndexes &Indexes, SmallVectorImpl< SlotIndex > &PHIKills)
Collect the ends of the predecessors where VNI is live-out into a PHI value of LR.
register Register static false bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, Register &Src, Register &Dst, unsigned &SrcSub, unsigned &DstSub)
SI Optimize VGPR LiveRange
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness)
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
bool test(unsigned Idx) const
Returns true if bit Idx is set.
Represents analyses that only rely on functions' control flow.
A helper class for register coalescers.
unsigned getDstIdx() const
Return the subregister index that DstReg will be coalesced into, or 0.
bool isFlipped() const
Return true when getSrcReg is the register being defined by the original copy instruction.
bool isPartial() const
Return true if the original copy instruction did not copy the full register, but was a subreg operati...
bool flip()
Swap SrcReg and DstReg.
bool isPhys() const
Return true if DstReg is a physical register.
bool isCrossClass() const
Return true if DstReg is virtual and NewRC is a smaller register class than DstReg's.
Register getDstReg() const
Return the register (virtual or physical) that will remain after coalescing.
bool isCoalescable(const MachineInstr *) const
Return true if MI is a copy instruction that will become an identity copy after coalescing.
const TargetRegisterClass * getNewRC() const
Return the register class of the coalesced register.
bool setRegisters(const MachineInstr *)
Set registers to match the copy instruction MI.
unsigned getSrcIdx() const
Return the subregister index that SrcReg will be coalesced into, or 0.
Register getSrcReg() const
Return the virtual register that will be coalesced away.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool isAsCheapAsAMove(const MachineInstr &MI) const override
A live range for subregisters.
LiveInterval - This class represents the liveness of a register, or stack slot.
LLVM_ABI void removeEmptySubRanges()
Removes all subranges without any segments (subranges without segments are not considered valid and s...
bool hasSubRanges() const
Returns true if subregister liveness information is available.
SubRange * createSubRangeFrom(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, const LiveRange &CopyFrom)
Like createSubRange() but the new range is filled with a copy of the liveness information in CopyFrom...
iterator_range< subrange_iterator > subranges()
LLVM_ABI void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask, std::function< void(LiveInterval::SubRange &)> Apply, const SlotIndexes &Indexes, const TargetRegisterInfo &TRI, unsigned ComposeSubRegIdx=0)
Refines the subranges to support LaneMask.
LLVM_ABI void computeSubRangeUndefs(SmallVectorImpl< SlotIndex > &Undefs, LaneBitmask LaneMask, const MachineRegisterInfo &MRI, const SlotIndexes &Indexes) const
For a given lane mask LaneMask, compute indexes at which the lane is marked undefined by subregister ...
SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)
Creates a new empty subregister live range.
LLVM_ABI void clearSubRanges()
Removes all subregister liveness information.
bool hasInterval(Register Reg) const
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
LLVM_ABI bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const
Returns true if VNI is killed by any PHI-def values in LI.
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
LLVM_ABI bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)
Test if LI is live across any register mask instructions, and compute a bit mask of physical register...
SlotIndexes * getSlotIndexes() const
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
VNInfo::Allocator & getVNInfoAllocator()
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
LiveInterval & getInterval(Register Reg)
LLVM_ABI void pruneValue(LiveRange &LR, SlotIndex Kill, SmallVectorImpl< SlotIndex > *EndPoints)
If LR has a live value at Kill, prune its live range by removing any liveness reachable from Kill.
void removeInterval(Register Reg)
Interval removal.
LiveRange & getRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit.
LLVM_ABI bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr, LaneBitmask SubRangeMask=LaneBitmask::getAll())
After removing some uses of a register, shrink its live range to just the remaining uses.
LLVM_ABI MachineBasicBlock * intervalIsInOneMBB(const LiveInterval &LI) const
If LI is confined to a single basic block, return a pointer to that block.
LiveRange * getCachedRegUnit(MCRegUnit Unit)
Return the live range for register unit Unit if it has already been computed, or nullptr if it hasn't...
LLVM_ABI void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos)
Remove value number and related live segments of LI and its subranges that start at position Pos.
LLVM_ABI void extendToIndices(LiveRange &LR, ArrayRef< SlotIndex > Indices, ArrayRef< SlotIndex > Undefs)
Extend the live range LR to reach all points in Indices.
LLVM_ABI void dump() const
LLVM_ABI void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const
SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI)
Result of a LiveRange query.
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
VNInfo * valueOut() const
Return the value leaving the instruction, if any.
VNInfo * valueDefined() const
Return the value defined by this instruction, if any.
SlotIndex endPoint() const
Return the end point of the last live range segment to interact with the instruction,...
bool isKill() const
Return true if the live-in value is killed by this instruction.
Callback methods for LiveRangeEdit owners.
SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false, unsigned SubIdx=0, MachineInstr *ReplaceIndexMI=nullptr, LaneBitmask UsedLanes=LaneBitmask::getAll())
rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...
void eliminateDeadDefs(SmallVectorImpl< MachineInstr * > &Dead, ArrayRef< Register > RegsBeingSpilled={})
eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...
This class represents the liveness of a register, stack slot, etc.
VNInfo * getValNumInfo(unsigned ValNo)
getValNumInfo - Returns pointer to the specified val#.
LLVM_ABI iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Segments::iterator iterator
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
LLVM_ABI void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, SmallVectorImpl< VNInfo * > &NewVNInfo)
join - Join two live ranges (this, and other) together.
bool liveAt(SlotIndex index) const
LLVM_ABI VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
LLVM_ABI void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarily including Idx,...
bool verify() const
Walk the range and assert if any invariants fail to hold.
LLVM_ABI VNInfo * MergeValueNumberInto(VNInfo *V1, VNInfo *V2)
MergeValueNumberInto - This method is called when two value numbers are found to be equivalent.
unsigned getNumValNums() const
bool containsOneValue() const
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
void assign(const LiveRange &Other, BumpPtrAllocator &Allocator)
Copies values numbers and live segments from Other into this range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
LLVM_ABI iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
bool contains(MCRegister Reg) const
contains - Return true if the specified register is included in this register class.
Wrapper class representing physical registers. Should be passed by value.
An RAII based helper class to modify MachineFunctionProperties when running pass.
bool isInlineAsmBrIndirectTarget() const
Returns true if this is the indirect dest of an INLINEASM_BR.
unsigned pred_size() const
LLVM_ABI bool hasEHPadSuccessor() const
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_ABI instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
LLVM_ABI iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
LLVM_ABI instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool verify(Pass *p=nullptr, const char *Banner=nullptr, raw_ostream *OS=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
const MachineInstrBuilder & addReg(Register RegNo, RegState Flags={}, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
LLVM_ABI void setRegisterDefReadUndef(Register Reg, bool IsUndef=true)
Mark all subregister defs of register Reg with the undef flag.
bool isImplicitDef() const
const MachineBasicBlock * getParent() const
bool isCopyLike() const
Return true if the instruction behaves like a copy.
filtered_mop_range all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
LLVM_ABI std::pair< bool, bool > readsWritesVirtualRegister(Register Reg, SmallVectorImpl< unsigned > *Ops=nullptr) const
Return a pair of bools (reads, writes) indicating if this instruction reads or writes Reg.
bool isRegTiedToDefOperand(unsigned UseOpIdx, unsigned *DefOpIdx=nullptr) const
Return true if the use operand of the specified index is tied to a def operand.
LLVM_ABI bool isSafeToMove(bool &SawStore) const
Return true if it is safe to move this instruction.
bool isDebugInstr() const
unsigned getNumOperands() const
Retuns the total number of operands.
LLVM_ABI void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool isRegTiedToUseOperand(unsigned DefOpIdx, unsigned *UseOpIdx=nullptr) const
Given the index of a register def operand, check if the register def is tied to a source operand,...
LLVM_ABI int findRegisterUseOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isKill=false) const
Returns the operand index that is a use of the specific register or -1 if it is not found.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
bool isCommutable(QueryType Type=IgnoreBundle) const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
LLVM_ABI void setDesc(const MCInstrDesc &TID)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one.
LLVM_ABI void substituteRegister(Register FromReg, Register ToReg, unsigned SubIdx, const TargetRegisterInfo &RegInfo)
Replace all occurrences of FromReg with ToReg:SubIdx, properly composing subreg indices where necessa...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
LLVM_ABI void removeOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with.
const MachineOperand & getOperand(unsigned i) const
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
LLVM_ABI MachineInstrBundleIterator< MachineInstr > eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
void setDebugLoc(DebugLoc DL)
Replace current source information with new such.
LLVM_ABI bool allDefsAreDead() const
Return true if all the defs of this instruction are dead.
MachineOperand * findRegisterDefOperand(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false)
Wrapper for findRegisterDefOperandIdx, it returns a pointer to the MachineOperand rather than an inde...
Analysis pass that exposes the MachineLoopInfo for a machine function.
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
LLVM_ABI void substVirtReg(Register Reg, unsigned SubIdx, const TargetRegisterInfo &)
substVirtReg - Substitute the current register with the virtual subregister Reg:SubReg.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setIsDead(bool Val=true)
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
void setIsKill(bool Val=true)
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
LLVM_ABI void substPhysReg(MCRegister Reg, const TargetRegisterInfo &)
substPhysReg - Substitute the current register with the physical register Reg, taking any existing Su...
void setIsUndef(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
LLVM_ABI bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
LLVM_ABI bool recomputeRegClass(Register Reg)
recomputeRegClass - Try to find a legal super-class of Reg's register class that still satisfies the ...
reg_instr_iterator reg_instr_begin(Register RegNo) const
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
LLVM_ABI LLVM_READONLY MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
iterator_range< use_nodbg_iterator > use_nodbg_operands(Register Reg) const
static reg_instr_iterator reg_instr_end()
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
bool reg_nodbg_empty(Register RegNo) const
reg_nodbg_empty - Return true if the only instructions using or defining Reg are Debug instructions.
use_instr_nodbg_iterator use_instr_nodbg_begin(Register RegNo) const
bool shouldTrackSubRegLiveness(const TargetRegisterClass &RC) const
Returns true if liveness for register class RC should be tracked at the subregister level.
LLVM_ABI void setRegClass(Register Reg, const TargetRegisterClass *RC)
setRegClass - Set the register class of the specified virtual register.
LLVM_ABI LaneBitmask getMaxLaneMaskForVReg(Register Reg) const
Returns a mask covering all bits that can appear in lane masks of subregisters of the virtual registe...
LLVM_ABI bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(Register Reg) const
defusechain_instr_iterator< true, true, false, true > reg_instr_iterator
reg_instr_iterator/reg_instr_begin/reg_instr_end - Walk all defs and uses of the specified register,...
LLVM_ABI const TargetRegisterClass * constrainRegClass(Register Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
iterator_range< use_iterator > use_operands(Register Reg) const
iterator_range< reg_instr_nodbg_iterator > reg_nodbg_instructions(Register Reg) const
Represent a mutable reference to an array (0 or more elements consecutively in memory),...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isProperSubClass(const TargetRegisterClass *RC) const
isProperSubClass - Returns true if RC has a legal super-class with more allocatable registers.
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
Wrapper class representing virtual and physical registers.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
constexpr unsigned id() const
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
bool isEarlyClobber() const
isEarlyClobber - Returns true if this is an early-clobber slot.
bool isValid() const
Returns true if this is a valid index.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
SlotIndex getPrevSlot() const
Returns the previous slot in the index list.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getIndexBefore(const MachineInstr &MI) const
getIndexBefore - Returns the index of the last indexed instruction before MI, or the start index of i...
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Returns the index past the last valid index in the given basic block.
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Returns the first index in the given basic block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
pointer data()
Return a pointer to the vector's buffer, even if empty().
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
static const unsigned CommuteAnyOperandIndex
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual bool enableJoinGlobalCopies() const
True if the subtarget should enable joining global copies.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
VNInfo - Value Number Information.
void markUnused()
Mark this value as unused.
BumpPtrAllocator Allocator
bool isUnused() const
Returns true if this value is unused.
unsigned id
The ID number of this value.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
static LLVM_ABI bool allUsesAvailableAt(const MachineInstr *MI, SlotIndex UseIdx, const LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetInstrInfo &TII)
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
This namespace contains all of the command line option processing machinery.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< DefNode * > Def
UseMask
Specifies the way the mask should be analyzed for undefs/poisonous elements in the shuffle mask.
This is an optimization pass for GlobalISel generic memory operations.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
LLVM_ABI char & RegisterCoalescerID
RegisterCoalescer - This pass merges live ranges to eliminate copies.
@ Kill
The last use of a register.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
LLVM_ABI Printable printRegUnit(MCRegUnit Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
auto unique(Range &&R, Predicate P)
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DWARFExpression::Operation Op
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
iterator_range< MIBundleOperands > mi_bundle_ops(MachineInstr &MI)
constexpr bool valueOr(BoolOrDefault X, bool Default)
LLVM_ABI void eraseInstrs(ArrayRef< MachineInstr * > DeadInstrs, MachineRegisterInfo &MRI, LostDebugLocObserver *LocObserver=nullptr)
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
@ End
Run the machine verifier once, at the end of the pipeline.
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
MCRegisterClass TargetRegisterClass
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static constexpr LaneBitmask getLane(unsigned Lane)
static constexpr LaneBitmask getAll()
constexpr bool any() const
static constexpr LaneBitmask getNone()
Remat - Information needed to rematerialize at a specific location.
This represents a simple continuous liveness interval for a value.