136 #include "llvm/Config/llvm-config.h"
149 #include <functional>
156 using namespace llvm;
158 #define DEBUG_TYPE "livedebugvalues"
160 STATISTIC(NumInserted,
"Number of DBG_VALUE instructions inserted");
213 static constexpr u32_location_t kUniversalLocation = 0;
217 static constexpr u32_location_t kFirstRegLocation = 1;
221 static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30;
225 static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation;
229 static constexpr u32_location_t kEntryValueBackupLocation =
230 kFirstInvalidRegLocation + 1;
232 LocIndex(u32_location_t Location, u32_index_t Index)
239 template<
typename IntT>
static LocIndex fromRawInteger(IntT
ID) {
240 static_assert(std::is_unsigned<IntT>::value &&
242 "Cannot convert raw integer to LocIndex");
243 return {
static_cast<u32_location_t
>(
ID >> 32),
244 static_cast<u32_index_t
>(
ID)};
250 return LocIndex(
Reg, 0).getAsRawInteger();
255 static auto indexRangeForLocation(
const VarLocSet &Set,
256 u32_location_t Location) {
257 uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
258 uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
259 return Set.half_open_range(Start, End);
270 class VarLocBasedLDV :
public LDVImpl {
282 enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
295 return SpillBase ==
Other.SpillBase && SpillOffset ==
Other.SpillOffset;
298 return !(*
this ==
Other);
312 enum class MachineLocKind {
319 enum class EntryValueLocKind {
320 NonEntryValueKind = 0,
322 EntryValueBackupKind,
323 EntryValueCopyBackupKind
324 } EVKind = EntryValueLocKind::NonEntryValueKind;
328 union MachineLocValue {
335 MachineLocValue() : Hash(0) {}
344 MachineLocValue
Value;
345 bool operator==(
const MachineLoc &Other)
const {
349 case MachineLocKind::SpillLocKind:
350 return Value.SpillLocation ==
Other.Value.SpillLocation;
351 case MachineLocKind::RegisterKind:
352 case MachineLocKind::ImmediateKind:
358 bool operator<(
const MachineLoc &Other)
const {
360 case MachineLocKind::SpillLocKind:
361 return std::make_tuple(
363 Value.SpillLocation.SpillOffset.getFixed(),
364 Value.SpillLocation.SpillOffset.getScalable()) <
366 Other.Kind,
Other.Value.SpillLocation.SpillBase,
367 Other.Value.SpillLocation.SpillOffset.getFixed(),
368 Other.Value.SpillLocation.SpillOffset.getScalable());
369 case MachineLocKind::RegisterKind:
370 case MachineLocKind::ImmediateKind:
390 : Var(
MI.getDebugVariable(),
MI.getDebugExpression(),
392 Expr(
MI.getDebugExpression()),
MI(
MI) {
393 assert(
MI.isDebugValue() &&
"not a DBG_VALUE");
394 assert((
MI.isDebugValueList() ||
MI.getNumOperands() == 4) &&
395 "malformed DBG_VALUE");
397 MachineLoc ML = GetLocForOp(
Op);
398 auto It =
find(Locs, ML);
399 if (It == Locs.end()) {
401 OrigLocMap.push_back(
MI.getDebugOperandIndex(&
Op));
405 unsigned OpIdx = Locs.size();
406 unsigned DuplicatingIdx = std::distance(Locs.begin(), It);
413 assert(EVKind != EntryValueLocKind::EntryValueKind &&
414 !isEntryBackupLoc());
421 Kind = MachineLocKind::RegisterKind;
422 Loc.RegNo =
Op.getReg();
423 }
else if (
Op.isImm()) {
424 Kind = MachineLocKind::ImmediateKind;
425 Loc.Immediate =
Op.getImm();
426 }
else if (
Op.isFPImm()) {
427 Kind = MachineLocKind::ImmediateKind;
428 Loc.FPImm =
Op.getFPImm();
429 }
else if (
Op.isCImm()) {
430 Kind = MachineLocKind::ImmediateKind;
431 Loc.CImm =
Op.getCImm();
442 assert(VL.Locs.size() == 1 &&
443 VL.Locs[0].Kind == MachineLocKind::RegisterKind);
444 VL.EVKind = EntryValueLocKind::EntryValueKind;
446 VL.Locs[0].Value.RegNo =
Reg;
458 assert(VL.Locs.size() == 1 &&
459 VL.Locs[0].Kind == MachineLocKind::RegisterKind);
460 VL.EVKind = EntryValueLocKind::EntryValueBackupKind;
473 assert(VL.Locs.size() == 1 &&
474 VL.Locs[0].Kind == MachineLocKind::RegisterKind);
475 VL.EVKind = EntryValueLocKind::EntryValueCopyBackupKind;
477 VL.Locs[0].Value.RegNo = NewReg;
483 static VarLoc CreateCopyLoc(
const VarLoc &OldVL,
const MachineLoc &OldML,
486 for (MachineLoc &ML : VL.Locs)
488 ML.Kind = MachineLocKind::RegisterKind;
489 ML.Value.RegNo = NewReg;
497 static VarLoc CreateSpillLoc(
const VarLoc &OldVL,
const MachineLoc &OldML,
500 for (MachineLoc &ML : VL.Locs)
502 ML.Kind = MachineLocKind::SpillLocKind;
503 ML.Value.SpillLocation = {SpillBase, SpillOffset};
514 assert(!isEntryBackupLoc() &&
515 "Tried to produce DBG_VALUE for backup VarLoc");
518 const auto &IID =
MI.getDesc();
524 for (
unsigned I = 0,
E = Locs.size();
I <
E; ++
I) {
525 MachineLocKind LocKind = Locs[
I].Kind;
526 MachineLocValue Loc = Locs[
I].Value;
529 case MachineLocKind::RegisterKind:
537 EVKind == EntryValueLocKind::EntryValueKind ? Orig.
getReg()
541 case MachineLocKind::SpillLocKind: {
546 unsigned Base = Loc.SpillLocation.SpillBase;
548 if (
MI.isNonListDebugValue()) {
552 Loc.SpillLocation.SpillOffset);
557 Ops.push_back(dwarf::DW_OP_deref);
563 case MachineLocKind::ImmediateKind: {
567 case MachineLocKind::InvalidKind:
571 return BuildMI(MF, DbgLoc, IID, Indirect, MOs, Var, DIExpr);
576 return Kind == MachineLocKind::ImmediateKind;
580 bool isEntryBackupLoc()
const {
581 return EVKind == EntryValueLocKind::EntryValueBackupKind ||
582 EVKind == EntryValueLocKind::EntryValueCopyBackupKind;
588 return EVKind == EntryValueLocKind::EntryValueBackupKind && usesReg(
Reg);
593 bool isEntryValueCopyBackupReg(
Register Reg)
const {
594 return EVKind == EntryValueLocKind::EntryValueCopyBackupKind &&
601 RegML.Kind = MachineLocKind::RegisterKind;
602 RegML.Value.RegNo =
Reg;
608 for (
unsigned Idx = 0; Idx < Locs.size(); ++Idx)
609 if (Locs[Idx].
Kind == MachineLocKind::RegisterKind &&
610 Register{
static_cast<unsigned>(Locs[Idx].Value.RegNo)} ==
Reg)
618 bool AnyRegs =
false;
619 for (
const auto &Loc : Locs)
620 if (Loc.Kind == MachineLocKind::RegisterKind) {
621 Regs.push_back(Loc.Value.RegNo);
627 bool containsSpillLocs()
const {
628 return any_of(Locs, [](VarLoc::MachineLoc ML) {
629 return ML.Kind == VarLoc::MachineLocKind::SpillLocKind;
635 bool usesSpillLoc(
SpillLoc SpillLocation)
const {
637 SpillML.Kind = MachineLocKind::SpillLocKind;
638 SpillML.Value.SpillLocation = SpillLocation;
644 unsigned getSpillLocIdx(
SpillLoc SpillLocation)
const {
645 for (
unsigned Idx = 0; Idx < Locs.size(); ++Idx)
646 if (Locs[Idx].
Kind == MachineLocKind::SpillLocKind &&
647 Locs[Idx].
Value.SpillLocation == SpillLocation)
655 return LS.dominates(
MI.getDebugLoc().get(), &
MBB);
658 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
662 for (
const MachineLoc &MLoc : Locs) {
663 if (Locs.begin() != &MLoc)
666 case MachineLocKind::RegisterKind:
669 case MachineLocKind::SpillLocKind:
670 Out <<
printReg(MLoc.Value.SpillLocation.SpillBase,
TRI);
671 Out <<
"[" << MLoc.Value.SpillLocation.SpillOffset.getFixed() <<
" + "
672 << MLoc.Value.SpillLocation.SpillOffset.getScalable()
676 case MachineLocKind::ImmediateKind:
677 Out << MLoc.Value.Immediate;
679 case MachineLocKind::InvalidKind:
684 Out <<
", \"" << Var.getVariable()->
getName() <<
"\", " << *Expr <<
", ";
685 if (Var.getInlinedAt())
690 if (isEntryBackupLoc())
691 Out <<
" (backup loc)\n";
698 return std::tie(EVKind, Var, Expr, Locs) ==
703 bool operator<(
const VarLoc &Other)
const {
704 return std::tie(Var, EVKind, Locs, Expr) <
720 std::map<VarLoc, LocIndices> Var2Indices;
728 LocIndices insert(
const VarLoc &VL) {
729 LocIndices &Indices = Var2Indices[VL];
731 if (!Indices.empty())
739 if (VL.EVKind == VarLoc::EntryValueLocKind::NonEntryValueKind) {
740 VL.getDescribingRegs(Locations);
743 return RegNo < LocIndex::kFirstInvalidRegLocation;
745 "Physreg out of range?");
746 if (VL.containsSpillLocs()) {
748 Locations.push_back(Loc);
750 }
else if (VL.EVKind != VarLoc::EntryValueLocKind::EntryValueKind) {
752 Locations.push_back(Loc);
754 Locations.push_back(LocIndex::kUniversalLocation);
764 LocIndices getAllIndices(
const VarLoc &VL)
const {
765 auto IndIt = Var2Indices.
find(VL);
766 assert(IndIt != Var2Indices.end() &&
"VarLoc not tracked");
767 return IndIt->second;
771 const VarLoc &operator[](LocIndex
ID)
const {
772 auto LocIt = Loc2Vars.
find(
ID.Location);
773 assert(LocIt != Loc2Vars.
end() &&
"Location not tracked");
774 return LocIt->second[
ID.Index];
780 struct TransferDebugPair {
787 using InstToEntryLocMap = std::multimap<const MachineInstr *, LocIndex>;
794 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
800 using VarToFragments =
806 const VarLocSet &CollectFrom,
807 const VarLocMap &VarLocIDs);
811 void getUsedRegs(
const VarLocSet &CollectFrom,
823 class OpenRangesSet {
834 : Alloc(Alloc), VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
836 const VarLocSet &getVarLocs()
const {
return VarLocs; }
844 const VarLocMap &VarLocIDs)
const {
845 collectAllVarLocs(Collected, VarLocs, VarLocIDs);
849 void erase(
const VarLoc &VL);
853 void erase(
const VarLocsInRange &KillSet,
const VarLocMap &VarLocIDs,
857 void insert(LocIndices VarLocIDs,
const VarLoc &VL);
860 void insertFromLocSet(
const VarLocSet &ToLoad,
const VarLocMap &Map);
868 EntryValuesBackupVars.
clear();
874 Vars.
empty() == VarLocs.empty() &&
875 "open ranges are inconsistent");
876 return VarLocs.empty();
880 auto getEmptyVarLocRange()
const {
887 return LocIndex::indexRangeForLocation(getVarLocs(),
Reg);
891 auto getSpillVarLocs()
const {
892 return LocIndex::indexRangeForLocation(getVarLocs(),
893 LocIndex::kSpillLocation);
898 auto getEntryValueBackupVarLocs()
const {
899 return LocIndex::indexRangeForLocation(
900 getVarLocs(), LocIndex::kEntryValueBackupLocation);
908 static void collectIDsForRegs(VarLocsInRange &Collected,
909 const DefinedRegsSet &Regs,
910 const VarLocSet &CollectFrom,
911 const VarLocMap &VarLocIDs);
914 std::unique_ptr<VarLocSet> &VLS = Locs[
MBB];
916 VLS = std::make_unique<VarLocSet>(Alloc);
921 const VarLocInMBB &Locs)
const {
922 auto It = Locs.find(
MBB);
923 assert(It != Locs.end() &&
"MBB not in map");
945 const DefinedRegsSet &Regs)
const;
954 VarLoc::SpillLoc extractSpillBaseRegAndOffset(
const MachineInstr &
MI);
955 void insertTransferDebugPair(
MachineInstr &
MI, OpenRangesSet &OpenRanges,
956 TransferMap &Transfers, VarLocMap &VarLocIDs,
957 LocIndex OldVarID, TransferKind
Kind,
958 const VarLoc::MachineLoc &OldLoc,
961 void transferDebugValue(
const MachineInstr &
MI, OpenRangesSet &OpenRanges,
962 VarLocMap &VarLocIDs,
963 InstToEntryLocMap &EntryValTransfers,
964 RegDefToInstMap &RegSetInstrs);
965 void transferSpillOrRestoreInst(
MachineInstr &
MI, OpenRangesSet &OpenRanges,
966 VarLocMap &VarLocIDs, TransferMap &Transfers);
968 OpenRangesSet &OpenRanges,
969 VarLocMap &VarLocIDs,
const VarLoc &EntryVL,
970 InstToEntryLocMap &EntryValTransfers);
971 void removeEntryValue(
const MachineInstr &
MI, OpenRangesSet &OpenRanges,
972 VarLocMap &VarLocIDs,
const VarLoc &EntryVL,
973 InstToEntryLocMap &EntryValTransfers,
974 RegDefToInstMap &RegSetInstrs);
976 VarLocMap &VarLocIDs,
977 InstToEntryLocMap &EntryValTransfers,
978 VarLocsInRange &KillSet);
980 const DefinedRegsSet &DefinedRegs,
981 OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
982 void transferRegisterCopy(
MachineInstr &
MI, OpenRangesSet &OpenRanges,
983 VarLocMap &VarLocIDs, TransferMap &Transfers);
984 void transferRegisterDef(
MachineInstr &
MI, OpenRangesSet &OpenRanges,
985 VarLocMap &VarLocIDs,
986 InstToEntryLocMap &EntryValTransfers,
987 RegDefToInstMap &RegSetInstrs);
989 VarLocInMBB &OutLocs,
const VarLocMap &VarLocIDs);
992 VarLocMap &VarLocIDs, TransferMap &Transfers,
993 InstToEntryLocMap &EntryValTransfers,
994 RegDefToInstMap &RegSetInstrs);
996 void accumulateFragmentMap(
MachineInstr &
MI, VarToFragments &SeenFragments,
1000 const VarLocMap &VarLocIDs,
1006 void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
1010 unsigned InputDbgValLimit)
override;
1019 void printVarLocInMBB(
const MachineFunction &MF,
const VarLocInMBB &V,
1020 const VarLocMap &VarLocIDs,
const char *msg,
1030 VarLocBasedLDV::VarLocBasedLDV() =
default;
1032 VarLocBasedLDV::~VarLocBasedLDV() =
default;
1039 void VarLocBasedLDV::OpenRangesSet::erase(
const VarLoc &VL) {
1042 auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
1043 auto It = EraseFrom->
find(VarToErase);
1044 if (It != EraseFrom->end()) {
1045 LocIndices IDs = It->second;
1046 for (LocIndex
ID : IDs)
1047 VarLocs.reset(
ID.getAsRawInteger());
1048 EraseFrom->erase(It);
1063 auto MapIt = OverlappingFragments.
find({Var.
getVariable(), ThisFragment});
1064 if (MapIt != OverlappingFragments.
end()) {
1065 for (
auto Fragment : MapIt->second) {
1074 void VarLocBasedLDV::OpenRangesSet::erase(
const VarLocsInRange &KillSet,
1075 const VarLocMap &VarLocIDs,
1077 VarLocSet RemoveSet(Alloc);
1079 const VarLoc &VL = VarLocIDs[LocIndex(Location,
ID)];
1080 auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
1081 EraseFrom->
erase(VL.Var);
1082 LocIndices VLI = VarLocIDs.getAllIndices(VL);
1083 for (LocIndex
ID : VLI)
1084 RemoveSet.set(
ID.getAsRawInteger());
1086 VarLocs.intersectWithComplement(RemoveSet);
1089 void VarLocBasedLDV::OpenRangesSet::insertFromLocSet(
const VarLocSet &ToLoad,
1090 const VarLocMap &Map) {
1091 VarLocsInRange UniqueVarLocIDs;
1092 DefinedRegsSet Regs;
1093 Regs.
insert(LocIndex::kUniversalLocation);
1094 collectIDsForRegs(UniqueVarLocIDs, Regs, ToLoad, Map);
1096 LocIndex Idx = LocIndex::fromRawInteger(
ID);
1097 const VarLoc &VarL =
Map[Idx];
1098 const LocIndices Indices =
Map.getAllIndices(VarL);
1099 insert(Indices, VarL);
1103 void VarLocBasedLDV::OpenRangesSet::insert(LocIndices VarLocIDs,
1105 auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
1106 for (LocIndex
ID : VarLocIDs)
1107 VarLocs.set(
ID.getAsRawInteger());
1108 InsertInto->
insert({VL.Var, VarLocIDs});
1114 VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(
DebugVariable Var) {
1115 auto It = EntryValuesBackupVars.
find(Var);
1116 if (It != EntryValuesBackupVars.
end())
1122 void VarLocBasedLDV::collectIDsForRegs(VarLocsInRange &Collected,
1123 const DefinedRegsSet &Regs,
1124 const VarLocSet &CollectFrom,
1125 const VarLocMap &VarLocIDs) {
1126 assert(!Regs.empty() &&
"Nothing to collect");
1130 auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front()));
1131 auto End = CollectFrom.end();
1136 uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(
Reg);
1137 uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(
Reg + 1);
1138 It.advanceToLowerBound(FirstIndexForReg);
1141 for (; It != End && *It < FirstInvalidIndex; ++It) {
1142 LocIndex ItIdx = LocIndex::fromRawInteger(*It);
1143 const VarLoc &VL = VarLocIDs[ItIdx];
1144 LocIndices LI = VarLocIDs.getAllIndices(VL);
1146 assert(LI.back().Location == LocIndex::kUniversalLocation &&
1147 "Unexpected order of LocIndices for VarLoc; was it inserted into "
1148 "the VarLocMap correctly?");
1149 Collected.insert(LI.back().Index);
1157 void VarLocBasedLDV::getUsedRegs(
const VarLocSet &CollectFrom,
1162 LocIndex::rawIndexForReg(LocIndex::kFirstRegLocation);
1164 LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation);
1165 for (
auto It = CollectFrom.find(FirstRegIndex),
1166 End = CollectFrom.find(FirstInvalidIndex);
1170 uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location;
1171 assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) &&
1172 "Duplicate used reg");
1173 UsedRegs.push_back(FoundReg);
1178 uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1);
1179 It.advanceToLowerBound(NextRegIndex);
1189 const VarLocInMBB &V,
1190 const VarLocMap &VarLocIDs,
1193 Out <<
'\n' << msg <<
'\n';
1197 const VarLocSet &L = getVarLocsInMBB(&
BB, V);
1201 collectAllVarLocs(VarLocs, L, VarLocIDs);
1202 Out <<
"MBB: " <<
BB.getNumber() <<
":\n";
1203 for (
const VarLoc &VL : VarLocs) {
1204 Out <<
" Var: " << VL.Var.getVariable()->getName();
1213 VarLocBasedLDV::VarLoc::SpillLoc
1214 VarLocBasedLDV::extractSpillBaseRegAndOffset(
const MachineInstr &
MI) {
1216 "Spill instruction does not have exactly one memory operand?");
1217 auto MMOI =
MI.memoperands_begin();
1220 "Inconsistent memory operand in spill instruction");
1221 int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1230 void VarLocBasedLDV::cleanupEntryValueTransfers(
1231 const MachineInstr *TRInst, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
1232 const VarLoc &EntryVL, InstToEntryLocMap &EntryValTransfers) {
1233 if (EntryValTransfers.empty() || TRInst ==
nullptr)
1236 auto TransRange = EntryValTransfers.equal_range(TRInst);
1237 for (
auto TDPair :
llvm::make_range(TransRange.first, TransRange.second)) {
1238 const VarLoc &EmittedEV = VarLocIDs[TDPair.second];
1239 if (std::tie(EntryVL.Var, EntryVL.Locs[0].Value.RegNo, EntryVL.Expr) ==
1240 std::tie(EmittedEV.Var, EmittedEV.Locs[0].Value.RegNo,
1242 OpenRanges.erase(EmittedEV);
1243 EntryValTransfers.erase(TRInst);
1254 OpenRangesSet &OpenRanges,
1255 VarLocMap &VarLocIDs,
1256 const VarLoc &EntryVL,
1257 InstToEntryLocMap &EntryValTransfers,
1258 RegDefToInstMap &RegSetInstrs) {
1260 if (&
MI == &EntryVL.MI)
1266 if (!
MI.getDebugOperand(0).isReg())
1272 if (
Reg.isValid() && RegSetInstrs.find(
Reg) != RegSetInstrs.end())
1273 TransferInst = RegSetInstrs.find(
Reg)->second;
1276 if (!TransferInst && !LastNonDbgMI &&
MI.getParent()->isEntryBlock())
1282 if (
MI.getDebugExpression()->getNumElements() == 0 && TransferInst) {
1289 auto DestSrc =
TII->isCopyInstr(*TransferInst);
1292 SrcRegOp = DestSrc->Source;
1293 DestRegOp = DestSrc->Destination;
1295 for (
uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
1296 const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(
ID)];
1297 if (VL.isEntryValueCopyBackupReg(
Reg) &&
1299 VL.MI.getDebugOperand(0).getReg() == SrcRegOp->
getReg())
1310 cleanupEntryValueTransfers(TransferInst, OpenRanges, VarLocIDs, EntryVL,
1312 OpenRanges.erase(EntryVL);
1318 OpenRangesSet &OpenRanges,
1319 VarLocMap &VarLocIDs,
1320 InstToEntryLocMap &EntryValTransfers,
1321 RegDefToInstMap &RegSetInstrs) {
1322 if (!
MI.isDebugValue())
1329 "Expected inlined-at fields to agree");
1335 auto EntryValBackupID = OpenRanges.getEntryValueBackup(V);
1337 const VarLoc &EntryVL = VarLocIDs[EntryValBackupID->back()];
1338 removeEntryValue(
MI, OpenRanges, VarLocIDs, EntryVL, EntryValTransfers,
1343 return (MO.isReg() && MO.getReg()) || MO.isImm() || MO.isFPImm() ||
1349 OpenRanges.erase(VL);
1351 LocIndices IDs = VarLocIDs.insert(VL);
1353 OpenRanges.insert(IDs, VL);
1354 }
else if (
MI.memoperands().size() > 0) {
1355 llvm_unreachable(
"DBG_VALUE with mem operand encountered after regalloc?");
1359 "Unexpected non-undef DBG_VALUE encountered");
1361 OpenRanges.erase(VL);
1367 const VarLocSet &CollectFrom,
1368 const VarLocMap &VarLocIDs) {
1372 uint64_t FirstIndex = LocIndex::rawIndexForReg(LocIndex::kUniversalLocation);
1374 LocIndex::rawIndexForReg(LocIndex::kUniversalLocation + 1);
1376 for (
auto It = CollectFrom.find(FirstIndex), End = CollectFrom.end();
1377 It != End && *It < FirstInvalidIndex; ++It) {
1378 LocIndex RegIdx = LocIndex::fromRawInteger(*It);
1379 Collected.push_back(VarLocIDs[RegIdx]);
1385 OpenRangesSet &OpenRanges,
1386 VarLocMap &VarLocIDs,
1387 InstToEntryLocMap &EntryValTransfers,
1388 VarLocsInRange &KillSet) {
1390 if (
MI.isTerminator())
1395 LocIndex Idx = LocIndex(LocIndex::kUniversalLocation,
ID);
1396 const VarLoc &VL = VarLocIDs[Idx];
1397 if (!VL.Var.getVariable()->isParameter())
1400 auto DebugVar = VL.Var;
1402 OpenRanges.getEntryValueBackup(DebugVar);
1406 if (!EntryValBackupIDs)
1409 const VarLoc &EntryVL = VarLocIDs[EntryValBackupIDs->back()];
1410 VarLoc EntryLoc = VarLoc::CreateEntryLoc(EntryVL.MI,
LS, EntryVL.Expr,
1411 EntryVL.Locs[0].Value.RegNo);
1412 LocIndices EntryValueIDs = VarLocIDs.insert(EntryLoc);
1413 assert(EntryValueIDs.size() == 1 &&
1414 "EntryValue loc should not be variadic");
1415 EntryValTransfers.insert({&
MI, EntryValueIDs.back()});
1416 OpenRanges.insert(EntryValueIDs, EntryLoc);
1425 void VarLocBasedLDV::insertTransferDebugPair(
1426 MachineInstr &
MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
1427 VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind
Kind,
1428 const VarLoc::MachineLoc &OldLoc,
Register NewReg) {
1429 const VarLoc &OldVarLoc = VarLocIDs[OldVarID];
1431 auto ProcessVarLoc = [&
MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
1432 LocIndices LocIds = VarLocIDs.insert(VL);
1435 OpenRanges.erase(VL);
1439 OpenRanges.insert(LocIds, VL);
1440 assert(!
MI.isTerminator() &&
"Cannot insert DBG_VALUE after terminator");
1441 TransferDebugPair MIP = {&
MI, LocIds.back()};
1442 Transfers.push_back(MIP);
1446 OpenRanges.erase(VarLocIDs[OldVarID]);
1448 case TransferKind::TransferCopy: {
1450 "No register supplied when handling a copy of a debug value");
1453 VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
1456 dbgs() <<
"Creating VarLoc for register copy:";
1461 case TransferKind::TransferSpill: {
1464 VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(
MI);
1465 VarLoc VL = VarLoc::CreateSpillLoc(
1466 OldVarLoc, OldLoc, SpillLocation.SpillBase, SpillLocation.SpillOffset);
1469 dbgs() <<
"Creating VarLoc for spill:";
1474 case TransferKind::TransferRestore: {
1476 "No register supplied when handling a restore of a debug value");
1479 VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
1482 dbgs() <<
"Creating VarLoc for restore:";
1493 OpenRangesSet &OpenRanges,
1494 VarLocMap &VarLocIDs,
1495 InstToEntryLocMap &EntryValTransfers,
1496 RegDefToInstMap &RegSetInstrs) {
1500 if (
MI.isMetaInstruction())
1508 DefinedRegsSet DeadRegs;
1514 !(
MI.isCall() && MO.
getReg() == SP)) {
1519 RegSetInstrs.erase(MO.
getReg());
1520 RegSetInstrs.insert({MO.
getReg(), &
MI});
1529 if (!RegMasks.empty()) {
1531 getUsedRegs(OpenRanges.getVarLocs(), UsedRegs);
1541 bool AnyRegMaskKillsReg =
1545 if (AnyRegMaskKillsReg)
1546 DeadRegs.insert(
Reg);
1547 if (AnyRegMaskKillsReg) {
1548 RegSetInstrs.erase(
Reg);
1549 RegSetInstrs.insert({
Reg, &
MI});
1554 if (DeadRegs.empty())
1557 VarLocsInRange KillSet;
1558 collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs(), VarLocIDs);
1559 OpenRanges.erase(KillSet, VarLocIDs, LocIndex::kUniversalLocation);
1563 if (
TM.Options.ShouldEmitDebugEntryValues())
1564 emitEntryValues(
MI, OpenRanges, VarLocIDs, EntryValTransfers, KillSet);
1571 if (!
MI.hasOneMemOperand())
1574 if (!
MI.getSpillSize(
TII) && !
MI.getFoldedSpillSize(
TII))
1583 if (!isSpillInstruction(
MI, MF))
1598 if (isKilledReg(MO,
Reg))
1604 auto NextI = std::next(
MI.getIterator());
1606 if (
MI.getParent()->end() == NextI)
1612 if (isKilledReg(MONext, RegNext) && RegNext ==
Reg)
1624 if (!
MI.hasOneMemOperand())
1629 if (
MI.getRestoreSize(
TII)) {
1630 Reg =
MI.getOperand(0).getReg();
1631 return extractSpillBaseRegAndOffset(
MI);
1643 void VarLocBasedLDV::transferSpillOrRestoreInst(
MachineInstr &
MI,
1644 OpenRangesSet &OpenRanges,
1645 VarLocMap &VarLocIDs,
1646 TransferMap &Transfers) {
1657 VarLocsInRange KillSet;
1658 if (isSpillInstruction(
MI, MF)) {
1659 Loc = extractSpillBaseRegAndOffset(
MI);
1660 for (
uint64_t ID : OpenRanges.getSpillVarLocs()) {
1661 LocIndex Idx = LocIndex::fromRawInteger(
ID);
1662 const VarLoc &VL = VarLocIDs[Idx];
1663 assert(VL.containsSpillLocs() &&
"Broken VarLocSet?");
1664 if (VL.usesSpillLoc(*Loc)) {
1676 unsigned SpillLocIdx = VL.getSpillLocIdx(*Loc);
1677 VarLoc::MachineLoc OldLoc = VL.Locs[SpillLocIdx];
1678 VarLoc UndefVL = VarLoc::CreateCopyLoc(VL, OldLoc, 0);
1679 LocIndices UndefLocIDs = VarLocIDs.insert(UndefVL);
1680 Transfers.push_back({&
MI, UndefLocIDs.back()});
1683 OpenRanges.erase(KillSet, VarLocIDs, LocIndex::kSpillLocation);
1688 if (isLocationSpill(
MI, MF,
Reg)) {
1689 TKind = TransferKind::TransferSpill;
1694 if (!(Loc = isRestoreInstruction(
MI, MF,
Reg)))
1696 TKind = TransferKind::TransferRestore;
1702 auto TransferCandidates = OpenRanges.getEmptyVarLocRange();
1703 if (TKind == TransferKind::TransferSpill)
1704 TransferCandidates = OpenRanges.getRegisterVarLocs(
Reg);
1705 else if (TKind == TransferKind::TransferRestore)
1706 TransferCandidates = OpenRanges.getSpillVarLocs();
1708 LocIndex Idx = LocIndex::fromRawInteger(
ID);
1709 const VarLoc &VL = VarLocIDs[Idx];
1711 if (TKind == TransferKind::TransferSpill) {
1712 assert(VL.usesReg(
Reg) &&
"Broken VarLocSet?");
1714 << VL.Var.getVariable()->getName() <<
")\n");
1717 assert(TKind == TransferKind::TransferRestore && VL.containsSpillLocs() &&
1718 "Broken VarLocSet?");
1719 if (!VL.usesSpillLoc(*Loc))
1723 << VL.Var.getVariable()->getName() <<
")\n");
1724 LocIdx = VL.getSpillLocIdx(*Loc);
1726 VarLoc::MachineLoc MLoc = VL.Locs[
LocIdx];
1727 insertTransferDebugPair(
MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind,
1739 OpenRangesSet &OpenRanges,
1740 VarLocMap &VarLocIDs,
1741 TransferMap &Transfers) {
1742 auto DestSrc =
TII->isCopyInstr(
MI);
1749 if (!DestRegOp->
isDef())
1754 if (CalleeSavedRegs.
test(*RAI))
1767 if (!isCalleeSavedReg(DestReg))
1774 for (
uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
1775 LocIndex Idx = LocIndex::fromRawInteger(
ID);
1776 const VarLoc &VL = VarLocIDs[Idx];
1777 if (VL.isEntryValueBackupReg(SrcReg)) {
1779 VarLoc EntryValLocCopyBackup =
1780 VarLoc::CreateEntryCopyBackupLoc(VL.MI,
LS, VL.Expr, DestReg);
1782 OpenRanges.erase(VL);
1785 LocIndices EntryValCopyLocIDs = VarLocIDs.insert(EntryValLocCopyBackup);
1786 OpenRanges.insert(EntryValCopyLocIDs, EntryValLocCopyBackup);
1795 for (
uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) {
1796 LocIndex Idx = LocIndex::fromRawInteger(
ID);
1797 assert(VarLocIDs[Idx].usesReg(SrcReg) &&
"Broken VarLocSet?");
1798 VarLoc::MachineLocValue Loc;
1800 VarLoc::MachineLoc MLoc{VarLoc::MachineLocKind::RegisterKind, Loc};
1801 insertTransferDebugPair(
MI, OpenRanges, Transfers, VarLocIDs, Idx,
1802 TransferKind::TransferCopy, MLoc, DestReg);
1811 OpenRangesSet &OpenRanges,
1812 VarLocInMBB &OutLocs,
1813 const VarLocMap &VarLocIDs) {
1814 bool Changed =
false;
1817 OpenRanges.getUniqueVarLocs(VarLocs, VarLocIDs);
1818 for (VarLoc &VL : VarLocs) {
1820 dbgs() <<
"Add to OutLocs in MBB #" << CurMBB->
getNumber() <<
": ";
1824 VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
1825 Changed = VLS != OpenRanges.getVarLocs();
1829 VLS = OpenRanges.getVarLocs();
1845 VarToFragments &SeenFragments,
1848 MI.getDebugLoc()->getInlinedAt());
1849 FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
1854 auto SeenIt = SeenFragments.find(MIVar.getVariable());
1855 if (SeenIt == SeenFragments.end()) {
1857 OneFragment.
insert(ThisFragment);
1858 SeenFragments.insert({MIVar.getVariable(), OneFragment});
1860 OverlappingFragments.
insert({{MIVar.getVariable(), ThisFragment}, {}});
1867 OverlappingFragments.
insert({{MIVar.getVariable(), ThisFragment}, {}});
1868 if (!IsInOLapMap.second)
1871 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
1872 auto &AllSeenFragments = SeenIt->second;
1877 for (
auto &ASeenFragment : AllSeenFragments) {
1881 ThisFragmentsOverlaps.push_back(ASeenFragment);
1884 auto ASeenFragmentsOverlaps =
1885 OverlappingFragments.
find({MIVar.getVariable(), ASeenFragment});
1886 assert(ASeenFragmentsOverlaps != OverlappingFragments.
end() &&
1887 "Previously seen var fragment has no vector of overlaps");
1888 ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1892 AllSeenFragments.insert(ThisFragment);
1896 void VarLocBasedLDV::process(
MachineInstr &
MI, OpenRangesSet &OpenRanges,
1897 VarLocMap &VarLocIDs, TransferMap &Transfers,
1898 InstToEntryLocMap &EntryValTransfers,
1899 RegDefToInstMap &RegSetInstrs) {
1900 if (!
MI.isDebugInstr())
1902 transferDebugValue(
MI, OpenRanges, VarLocIDs, EntryValTransfers,
1904 transferRegisterDef(
MI, OpenRanges, VarLocIDs, EntryValTransfers,
1906 transferRegisterCopy(
MI, OpenRanges, VarLocIDs, Transfers);
1907 transferSpillOrRestoreInst(
MI, OpenRanges, VarLocIDs, Transfers);
1913 bool VarLocBasedLDV::join(
1915 const VarLocMap &VarLocIDs,
1920 VarLocSet InLocsT(Alloc);
1932 LLVM_DEBUG(
dbgs() <<
" ignoring unvisited pred MBB: " <<
p->getNumber()
1936 auto OL = OutLocs.find(
p);
1938 if (OL == OutLocs.end())
1943 VarLocSet &OutLocVLS = *OL->second;
1945 InLocsT = OutLocVLS;
1947 InLocsT &= OutLocVLS;
1950 if (!InLocsT.empty()) {
1952 collectAllVarLocs(VarLocs, InLocsT, VarLocIDs);
1953 for (const VarLoc &VL : VarLocs)
1954 dbgs() <<
" gathered candidate incoming var: "
1955 << VL.Var.getVariable()->getName() <<
"\n";
1963 VarLocSet KillSet(Alloc);
1964 bool IsArtificial = ArtificialBlocks.
count(&
MBB);
1965 if (!IsArtificial) {
1967 LocIndex Idx = LocIndex::fromRawInteger(
ID);
1971 auto Name = VarLocIDs[Idx].Var.getVariable()->
getName();
1972 dbgs() <<
" killing " <<
Name <<
", it doesn't dominate MBB\n";
1977 InLocsT.intersectWithComplement(KillSet);
1983 "Should have processed at least one predecessor");
1985 VarLocSet &ILS = getVarLocsInMBB(&
MBB, InLocs);
1986 bool Changed =
false;
1987 if (ILS != InLocsT) {
1995 void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
1996 VarLocMap &VarLocIDs) {
1999 for (
auto &Iter : PendingInLocs) {
2002 VarLocSet &Pending = *Iter.second;
2005 collectAllVarLocs(VarLocs, Pending, VarLocIDs);
2007 for (VarLoc DiffIt : VarLocs) {
2010 if (DiffIt.isEntryBackupLoc())
2021 bool VarLocBasedLDV::isEntryValueCandidate(
2022 const MachineInstr &
MI,
const DefinedRegsSet &DefinedRegs)
const {
2023 assert(
MI.isDebugValue() &&
"This must be DBG_VALUE.");
2029 auto *DIVar =
MI.getDebugVariable();
2030 if (!DIVar->isParameter())
2034 if (
MI.getDebugLoc()->getInlinedAt())
2047 if (DefinedRegs.count(
MI.getDebugOperand(0).getReg()))
2052 if (
MI.getDebugExpression()->getNumElements() > 0)
2071 const DefinedRegsSet &DefinedRegs,
2072 OpenRangesSet &OpenRanges,
2073 VarLocMap &VarLocIDs) {
2076 if (!
TM.Options.ShouldEmitDebugEntryValues())
2081 MI.getDebugLoc()->getInlinedAt());
2083 if (!isEntryValueCandidate(
MI, DefinedRegs) ||
2084 OpenRanges.getEntryValueBackup(V))
2093 VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(
MI,
LS,
NewExpr);
2094 LocIndices EntryValLocIDs = VarLocIDs.insert(EntryValLocAsBackup);
2095 OpenRanges.insert(EntryValLocIDs, EntryValLocAsBackup);
2103 unsigned InputDbgValLimit) {
2123 bool Changed =
false;
2124 bool OLChanged =
false;
2125 bool MBBJoined =
false;
2127 VarLocMap VarLocIDs;
2129 OpenRangesSet OpenRanges(Alloc, OverlapFragments);
2131 VarLocInMBB OutLocs;
2133 TransferMap Transfers;
2136 InstToEntryLocMap EntryValTransfers;
2138 RegDefToInstMap RegSetInstrs;
2140 VarToFragments SeenFragments;
2148 std::priority_queue<unsigned int, std::vector<unsigned int>,
2149 std::greater<unsigned int>>
2151 std::priority_queue<unsigned int, std::vector<unsigned int>,
2152 std::greater<unsigned int>>
2157 DefinedRegsSet DefinedRegs;
2162 for (
auto &
MI : First_MBB) {
2164 if (
MI.isDebugValue())
2165 recordEntryValue(
MI, DefinedRegs, OpenRanges, VarLocIDs);
2169 for (
auto &
MBB : MF)
2170 for (
auto &
MI :
MBB)
2171 if (
MI.isDebugValue())
2172 accumulateFragmentMap(
MI, SeenFragments, OverlapFragments);
2174 auto hasNonArtificialLocation = [](
const MachineInstr &
MI) ->
bool {
2176 return DL.getLine() != 0;
2179 for (
auto &
MBB : MF)
2183 LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
2184 "OutLocs after initialization",
dbgs()));
2187 unsigned int RPONumber = 0;
2189 OrderToBB[RPONumber] =
MBB;
2190 BBToOrder[
MBB] = RPONumber;
2191 Worklist.push(RPONumber);
2196 unsigned NumInputDbgValues = 0;
2197 for (
auto &
MBB : MF)
2198 for (
auto &
MI :
MBB)
2199 if (
MI.isDebugValue())
2200 ++NumInputDbgValues;
2201 if (NumInputDbgValues > InputDbgValLimit) {
2202 LLVM_DEBUG(
dbgs() <<
"Disabling VarLocBasedLDV: " << MF.getName()
2203 <<
" has " << RPONumber <<
" basic blocks and "
2204 << NumInputDbgValues
2205 <<
" input DBG_VALUEs, exceeding limits.\n");
2215 while (!Worklist.empty() || !Pending.empty()) {
2221 while (!Worklist.empty()) {
2224 MBBJoined = join(*
MBB, OutLocs, InLocs, VarLocIDs, Visited,
2226 MBBJoined |= Visited.
insert(
MBB).second;
2234 OpenRanges.insertFromLocSet(getVarLocsInMBB(
MBB, InLocs), VarLocIDs);
2235 LastNonDbgMI =
nullptr;
2236 RegSetInstrs.clear();
2237 for (
auto &
MI : *
MBB)
2238 process(
MI, OpenRanges, VarLocIDs, Transfers, EntryValTransfers,
2240 OLChanged |= transferTerminator(
MBB, OpenRanges, OutLocs, VarLocIDs);
2242 LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
2243 "OutLocs after propagating",
dbgs()));
2244 LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
2245 "InLocs after propagating",
dbgs()));
2250 if (OnPending.
insert(
s).second) {
2251 Pending.push(BBToOrder[
s]);
2256 Worklist.swap(Pending);
2259 assert(Pending.empty() &&
"Pending should be empty");
2263 for (
auto &TR : Transfers) {
2264 assert(!TR.TransferInst->isTerminator() &&
2265 "Cannot insert DBG_VALUE after terminator");
2267 const VarLoc &VL = VarLocIDs[TR.LocationID];
2274 for (
auto &TR : EntryValTransfers) {
2277 "Cannot insert DBG_VALUE after terminator");
2279 const VarLoc &VL = VarLocIDs[TR.second];
2283 EntryValTransfers.clear();
2287 flushPendingLocs(InLocs, VarLocIDs);
2289 LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
"Final OutLocs",
dbgs()));
2290 LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
"Final InLocs",
dbgs()));
2297 return new VarLocBasedLDV();